139. Word Break

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {    
        
        // wordBreak[i]: if substring(0, i) is within the dictionary
        boolean[] wordBreak = new boolean[s.length() + 1];
        wordBreak[0] = true;
        
        // wordBreak[i] is true if [0, j] is true and [j, i] is in dict
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (wordBreak[j] && wordDict.contains(s.substring(j, i))) {
                    wordBreak[i] = true;
                    break;
                }
            }
        }
        return wordBreak[s.length()];
    }
}