LeetCode 139 Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, givens = "leetcode",dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
上來直接用一個brute force织中，遍歷字符串如果找到一個單詞牡昆，繼續(xù)recursion搜索剩余的字符串枯冈，果斷超時一罩。。挪鹏。
參考了一下dp的思路月而。馋嗜。麸俘。對于最優(yōu)子結(jié)構(gòu)的理解還是不夠到位１缁！
這題的最優(yōu)子結(jié)構(gòu)在于：
假設(shè)字符串lookforthebestworld从媚，用dp[]數(shù)組記錄到某一位為止是否是validWords逞泄，則dp[0]-dp[3]都是false，dp[4]是true因為出現(xiàn)了第一個單詞look０菪АＥ缰凇！只有此時紧憾，才繼續(xù)判斷后續(xù)字符串forthebestworld到千。
代碼：
public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
int n = s.length();
if (n == 0) return false;
boolean[] valid = new boolean[n+1];
valid[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (valid[j] && wordDict.contains(s.substring(j,i))) {
valid[i] = true;
break;
}
}
}
return valid[n];
}
}
參考：
https://discuss.leetcode.com/topic/6156/java-implementation-using-dp-in-two-ways/3
