Dictionary Word 1

Given a word and a dictionary, determine if it can be composed by concatenating words from the given dictionary.

Assumptions

• The given word is not null and is not empty

• The given dictionary is not null and is not empty and all the words in the dictionary are not null or empty

Examples

Dictionary: {“bob”, “cat”, “rob”}

• Word: “robob” return false

• Word: “robcatbob” return true since it can be composed by "rob", "cat", "bob"

Solution: DP, incremental check string

Base Case: M[0] = true;

Induction Rule:

1. Check each increment

2. Check each cut of every increment

3. if left cut && right cut both are words, set current increment to true

public boolean canBreak(String input, String[] dict){
    boolean[] m = new boolean[input.length() + 1];
    m[0] = true;
    Set<String> dictionary = new HashSet<>(Arrays.asList(dict));
    
    for (int i = 1; i <= m.length; i++){ //check every increment
        for (int j = 0; j < i; j++){ //check every cut of every increment
            if (m[j] && dictionary.contains(input.substring(j, i))){
                m[j] = true;
                break;
             }
         }
     }
     return m[m.length - 1];
}   

Time complexity: O(N) increment check * O(N) cut check * O(N) String.substring Api = O(N^3)

Space Complexity: O(input size + dict size)