How to check if a word can be composed of entries in an array?

Question

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?

Answer 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()];
        }