lintcode107- Word Break- medium

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

算法：用DP。f[x]定义为substring(0,x)能不能break。f[x] = {f[i] && dict.contains(substring(i, x))} | 对所有x之前，末尾单词substring(i,x)长度是小于最长单词长度的。

第二个空间优化（避免MLE）：

1.避免写递归DFS（和Palindrome partitioning很像，都是如果求全部答案的话用DFS，但如果只求一个最优答案所需要的步数用DP。）

2.避免写出遍历所有长度substring的写法，因为substring用的空间复杂度时间复杂度是和string长度成正比的，这里要做一个只需要遍历dict里面最长单词长度的substring的优化(因为长度更长的单词肯定不会存在dict里了，没必要看)。

细节：小心cornercase s == ""。这种不但要考虑dict为空，比较字符串也要考虑为空。

1.DP。

public class Solution {
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
    public boolean wordBreak(String s, Set<String> dict) {
        // write your code here
        
        if (dict == null) {
            return false;
        }
        if (s.equals("")) {
            return true;
        }
        
        int maxLength = Integer.MIN_VALUE;
        for (String word : dict) {
            maxLength = Math.max(maxLength, word.length());
        }
        // canBreak[i] 代表s.substring(0,i+1)能不能被break, 0< i < s.length() 
        boolean[] canBreak = new boolean[s.length() + 1];
        canBreak[0] = true;
        // 问题就在于不能直接遍历所有长度的substring!那就会超空间复杂度，要做一个调查substring长度小于maxLength的优化！！！！
        
        // for (int i = 0; i < s.length(); i++) {
        //     if (dict.contains(s.substring(0, i + 1))) {
        //         canBreak[i] = true;
        //     }
        // }
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - maxLength; j < i; j++) {
                if (j < 0) {
                    continue;
                }
                if (canBreak[j] && dict.contains(s.substring(j, i))) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[s.length()];
    }
    
    
}

2.递归写法（爆了MLE）

public class Solution {
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
    public boolean wordBreak(String s, Set<String> dict) {
        // write your code here
        
        if (dict == null) {
            return false;
        }
        
        if (dict.contains(s) || s.equals("")) {
            return true;
        }
        
        for (int i = 1; i < s.length(); i++) {
            if (dict.contains(s.substring(0, i)) && wordBreak(s.substring(i, s.length()), dict)) {
                return true;
            }
        }
        
        return false;
    }
    
    
}