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