[DP]139. Word Break

139. Word Break
动规，时间复杂度O(n^2)，空间复杂度O(n)

For example, given

dict = ["leet", "code"].
Return true 

because "leetcode" can be segmented as "leet code".

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
//         ～DP～
        if(wordDict.contains(s)) return true;
        
        //inDict[i] 即 0－－i substring都可以在wordDict中找到，最终目标是返回inDict[s.length()-1]
        boolean[] inDict = new boolean[s.length()];
        for(int i = 1; i <= s.length() ;i++){   
            for(int j = 0; j < i; j++){
                //0---i串分为两个子串, 0---j-1,j---i
                if(( j == 0 || inDict[j-1]) && wordDict.contains(s.substring(j,i)) ){ //注意要把 j == 0判断放左边，防止OutofIndex
                    //最后一个单词j---i，和最后一个单词前的所有单词子串0---j-1，都在Dict中，则该子串必在Dict中。
                    inDict[i-1] = true;
                    break;
                }
            }
            
        }
        return inDict[s.length()-1];
        
    }
}