139. Word Break
動(dòng)規(guī)露乏，時(shí)間復(fù)雜度O(n^2)，空間復(fù)雜度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中找到市埋，最終目標(biāo)是返回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串分為兩個(gè)子串, 0---j-1,j---i
if(( j == 0 || inDict[j-1]) && wordDict.contains(s.substring(j,i)) ){ //注意要把 j == 0判斷放左邊柑潦，防止OutofIndex
//最后一個(gè)單詞j---i淑蔚，和最后一個(gè)單詞前的所有單詞子串0---j-1，都在Dict中勘究，則該子串必在Dict中矮湘。
inDict[i-1] = true;
break;
}
}
}
return inDict[s.length()-1];
}
}
