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，遍历字符串如果找到一个单词，继续recursion搜索剩余的字符串，果断超时。。。
参考了一下dp的思路。。。对于最优子结构的理解还是不够到位！！
这题的最优子结构在于：
假设字符串lookforthebestworld，用dp[]数组记录到某一位为止是否是validWords，则dp[0]-dp[3]都是false，dp[4]是true因为出现了第一个单词look！！！只有此时，才继续判断后续字符串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
