-3

I have the following task:

A word "Superhighway" is given. Check if such word can be composed of entries in the array: [ab, bc, Super, h, igh, way] - yes; [ab, bc, Super, way] - no;

My suggestion is to build Trie from the array and based on the Trie conclude can the target word be derived or not.

Also, I've seen that Dynamic Programming is applicable to similar problems.

Could you please explain the best solution for the task?

Pasha
  • 1,768
  • 6
  • 22
  • 43
  • I would suggest that you start working on your own suggestion and come back when you encounter any problems. This is a little too broad and consists of nothing but your assignment. – f1sh May 14 '19 at 11:16
  • @f1sh I would suggest you delete your comment. It's not my assignment, it's a question from my recent interview at Amazon – Pasha May 14 '19 at 11:17
  • 1
    @Pavel f1sh's comment was spot on. You tried nothing. Just because it wasn't for school: you want the answer, you have the question -> that's what an assignment is. – Stultuske May 14 '19 at 11:18
  • Post some code showing you actually tried something. – DougM May 14 '19 at 11:20
  • 2
    Then it would be a question to CodeReview. What's the diff between my question and https://stackoverflow.com/questions/4355955/subset-sum-algorithm Go ahead and close his post – Pasha May 14 '19 at 11:21
  • 1
    @Pavel Trie would make it complex and not sure if it would work. Dynamic programming is most suitable in my opinion. – nice_dev May 14 '19 at 11:30

1 Answers1

1

Dynamic programming should be applied here. The optimal substructure here is:

dp[i]: if s[0, i) can be composed of entries in the provide array.

dp[i] |= dp[j] && (s[j, i) is an entry in the array).

        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> wordDictSet = new HashSet(wordDict);
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 0; j < i; j++) {
                    if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
Lyn
  • 637
  • 5
  • 16