> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dynamic-programming/dictionary-word-1.md).

# 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)