139. Word Break

O(n^3)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return dfs(s, 0, wordDict, new Boolean[s.length()]);
    }
    private boolean dfs(String s, int start, List<String> wordDict, Boolean[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (String w : wordDict) {
            int len = w.length();
            if (start + len > s.length()) { // can be s.length() -> in next call, go to base condition
                continue;
            }
            String sub = s.substring(start, start + len);
            if (w.equals(sub)) {
                if (dfs(s, start + len, wordDict, memo)) {
                    return memo[start] = true;
                }
            }
        }
        return memo[start] = false;
    }
}

/*
is s composed from dict?

function (s, wordDict)
    for (String w : wordDict ) {
        if (s has prefix == w) {
            if (dfs(s remove prefix, wordDict)) {
                return true
            }
        }
    }
}
*/

T: O(n^3)

S: O(m), wordDict size

```java
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        return dfs(s, 0, dict, new Boolean[s.length()+1]);
    }
    private boolean dfs(String s, int start, Set<String> dict, Boolean[] memo) {
        if (s.length() == start) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int i = start + 1; i <= s.length(); i++) { // O(n^2), substring also need O(n)
            String sub = s.substring(start, i);
            if (dict.contains(sub) && dfs(s, i, dict, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }
}

/*
before memo:
遞歸調用(dfs): O(2^n) , 切或不切
總的時間複雜度依然是指數級的O(2^N * N^2)

after memo：
made O(2^n) to O(N), 狀態的個數
使得遞歸函數的調用次數從指數級別降低為狀態的個數O(N)，函數本身的複雜度還是O(N^2)，所以總的時間複雜度是O(N^3)

*/
```