140. Word Break II

看起来像backtrack。。

实际上也就是。

有一个TEST CASE令我们必须先判断String是不是可分的，从而导致我不得不把word break I的办法拿来用，正好复习下。。

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if (s.length() == 0) return res;
        
        
        if (!isBreakable(s, wordDict)) return res;
        
        helper(s, wordDict, new String(), res);
        return res;
        
    }
    
    public void helper(String s, Set<String> wordDict, String tempStr, List<String> res) {
        if (s.length() == 0) {
            res.add(new String(tempStr.trim()));
            return;
        } else {
            for (int i = 1; i <= s.length(); i++) {
                if (wordDict.contains(s.substring(0,i)) && isBreakable(s.substring(i), wordDict)) {
                    helper(s.substring(i), wordDict, tempStr + " " + s.substring(0,i), res);
                }
            }
            return;
        }
    }
    
    public boolean isBreakable(String s, Set<String> wordDict) {
        if (s.length() == 0) return true;
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 0; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j,i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
}

这两天在准备面经，没怎么刷题。。

明天面试啦。。加油哇。。保佑出个我做过的题吧。。。

哇呀呀~ 我 生 气 啦~~

---

二刷。

backtrack暴力搜索= =

一个String能拆得是这样。。

0-i的左边得是一个单词，i-n的右边得能拆= = 能拆i-n继续下一层.

能不能拆的判断需要139的解法。

Time:
能不能拆算是O(2^n) 后面得这样算。。

T(n) = T(n-1) + T(n-2) + ... + T(0)
T(n-1) = T(n-2) + T(n-3) + ... +　T(0)
T(n) = 2T(n-1) = 4T(n-2) ... (2^n)T(1)

T(1) = O(2^n)..so

so..Time compexity : O(2^n)?

139我可以确定是O(2^n)，这个肯定比那个大= =

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<>();
        
        if (!isBreakable(s, wordDict)) {
            return res;
        }
        
        dfs(res, s, wordDict, new StringBuilder());
        
        return res;
    }
    
    public void dfs(List<String> res, String s, Set<String> set, StringBuilder sb) {
        if (s.length() == 0) {
            res.add(sb.toString().trim());
            return;
        } else {
            int len = sb.length();
            for (int i = 1; i <= s.length(); i++) {
                if (set.contains(s.substring(0,i)) && isBreakable(s.substring(i), set)) {
                    sb.append(s.substring(0, i) + " ");
                    dfs(res, s.substring(i), set, sb);
                    sb.setLength(len);
                }
            }
        }
    }
    
    public boolean isBreakable(String s, Set<String> set) {
        if (s.length() == 0) return true;
        
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
    
    
}