DP/DFS - LC139/140 Word Break

第一题是确定是否可以断句，第二题是输出所有断句的可能性。第二题可以用到了第一题的判读来加速，是否进行Solution的check。

class Solution {
    public static String empty = " ";
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet(wordDict.size());
        int min = Integer.MAX_VALUE, max = 0;
        for(String word : wordDict){
            int l = word.length();
            min = Integer.min(l, min);
            max = Integer.max(l, max);
            set.add(word);
        }
        
        if(hasSolution(s, set, min, max)){
            List<List<String>> dp = new ArrayList<>(s.length() + 1);
            for(int i = 0; i <= s.length(); i++) dp.add(new ArrayList()); // init dp with emply array
            dp.get(s.length()).add("");
            for(int i = s.length() - 1; i >= 0; --i) {
                for(int j = i + 1; j <= s.length(); ++j) {
                    int l = j - i;
                    String check = s.substring(i, j);
                    if (l >= min && l <= max && set.contains(check)) {
                        for(String word : dp.get(j)) {
                            dp.get(i).add(check.concat(word.isEmpty() ? word : (empty + word)));
                        }
                    }
                }
            }
            return dp.get(0);
        }
        
        return new ArrayList();
    }
    
    //LC 139 solution
    public boolean hasSolution(String s, Set<String> set, int min, int max){
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = min; i <= s.length(); ++i){
            for(int j = 0; j < i; ++j){
                int l = i - j;
                if(dp[j] && l >= min && l <= max && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

   //超时的简洁版DFS判断是否有Solution
    public boolean dfs(String s, Set<String> set, int min, int max){
        if(s.isEmpty()) return true;
        for(int j = min; j <= max && j <= s.length(); ++j){
            if(set.contains(s.substring(0, j)) && dfs(s.substring(j, s.length()), set, min, max)){
                return true;
            }
        }
        return false; 
    }