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];
}
}
