139 Word Break.java

/*Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, 
determine if s can be segmented into a space-separated sequence of one or more dictionary words. 
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.*/

//1. 参数中dict为set
//1（1）DP
// 时间 近似O(n^2)，实际O(n*maxLen) n为String长度
//空间 O(n)
public boolean wordBreak(String s, Set<String> dict) {
        if(s == null || s.length() == 0){ //""是任意字符串的子串
            return true;
        }
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        int maxLen = 0;
        for(String str: dict){  //求maxLen是为了优化，缩小下面dp时候j的循环范围
            maxLen = Math.max(maxLen, str.length());
        }
        for(int i = 1; i <= s.length(); i++){
            for(int j = i - 1; j >= 0 && i - j <= maxLen; j--){ //倒着循环
                //此处记得加条件 i-j<=maxLen (相当于优化：减少循环次数，不然超时)
                if(dp[j] && dict.contains(s.substring(j, i))){ //substring(j, i)是指下标从j到i-1段的子串。即[j,i)。长度为 i - j
                    dp[i] = true;
                    break; //break
                }
            }
        }
        return dp[s.length()];
    }
//1（2）DFS 和follow up的一样
// 2. 参数中dict类型改为List
// 另外写一个函数isInDict()来代替set.contains()即可。其他地方相同。时间复杂度增加一点O(m) m=size of dict
 public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i <= s.length(); i++){
            for(int j = i - 1; j >= 0 ; j--){
                if(dp[j] && isInDict(s.substring(j, i), wordDict)){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
     public boolean isInDict(String s, List<String> dict){
            for(String str: dict){
                if(str.equals(s)){ //注意不要用等号
                    return true;
                }
            }
           return false;
        }

//follow-up：返回任意一组解 (140. Word Break II 要求返回所有解 (hard))
// 1. DFS返回一个解:
//时间： 字典长度 的 string长度 次方  字典长度*字典长度*字典长度*字典长度……
//O(C^K)=O((lengthOfString/dictWordLength)^lengthOfString)=O(dictWordLength^lengthOfString) time, O(lengthOfString) stack space
public class Solution {
    public String wordBreak(String s, Set<String> dict) {
        String res = "";
        if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
            return res;
        }
        helper(res, s, dict, "", 0);
        return res;
    }
    
    private boolean helper(List<String> res, String s, Set<String> dict, String path, int index) { //返回值boolean即可
      //从index开始的子串，是否可以分割成字典词的组成
        if (index == s.length()) { //起始点已经循环到String最末尾了，可以出口了
            res.add(path.substring(1));//one solution found 从1开始的子串即可，因为path第一个元素为" "
            return true;
        }
        for (int i = index + 1; i <= s.length(); i++) { //i相当于右指针。word的结束下标。
            String word = s.substring(index, i); //从index到i(不含)组成word
            if (dict.contains(word) && helper(res, s, dict, path + " " + word, i)) {//包括现在的word，以及index挪到i开始往后搜寻，也是true
                return true; //！和后面题的不同处在上面一行： helper()在判断条件里，同时满足的时候返回true
            }
        }
    }
}

//2. dp返回一个解
// 时间 ：O(n*maxLen) 不到O(n^2)  和只返回boolean的算法时间复杂度一样
// 空间： O(n) 一个dp数组
//O(lengthOfString * maxLength) time and O(lengthOfString) space
public class Solution {
    public String wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
            return true;
        }
        int maxLength = getMaxLength(dict);
        boolean[] dp = new boolean[s.length() + 1];//dp[i]:whether 0 to i part of string can be segmented into words in dict
        int[] index = new int[s.length() + 1];//index[i]:index of the end of a dict's word s.substr(i, index[i])
        dp[0] = true;
        words[0] = -1;
        for (int i = 1; i <= s.length(); i++) {//O(n) * O(maxLength)
            for (int lastWordLength = 1; lastWordLength <= maxLength && lastWordLength <= i; lastWordLength++) {//<= i !!!
                if (dp[i - lastWordLength] && dict.contains(s.substring(i - lastWordLength, i))) {//need add s.substring !!!
                    dp[i] = true;//if string from 0 to i-lastWordLength is segmentable, and i-lastWordLength to i is in dict
                    index[i - lastWordLength] = i;//record the index of breaking position 记录单词划分的位置
                    break;//eg. 0 L E E T C O D E -> L(F),i++ -> E(F),LE(F),i++ -> E(F),EE(F),LEE(F),i++ -> .....,LEET(T)
                }         //    T F F F T F F F T
            }
        }
        if (!dp[s.length()]) {//remember to check dp[s.length()] first !!!无解直接返回
            return "";
        }
            //以下构造最后的句子
        StringBuilder sb = new StringBuilder(s.substring(0, index[0]));
        int start = index[0];
        while (start != s.length()) {
            sb.append(" " + s.substring(start, index[start])); 
            start = index[start];//remember to update start !!!
        }
        return sb.toString();
    }
    
    private int getMaxLength(Set<String> dict) {
        int max = 0;
        for (String s : dict) {
            max = Math.max(max, s.length());
        }
        return max;
    }
}

//3.DFS返回所有解 (可能会超时)
//和一个解略有区别：递归执行的位置。
//返回一个解的：满足条件contains && helper()时，return true；返回所有解的：满足条件contains，执行helper()
public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
            return res;
        }
        helper(res, s, dict, "", 0);
        return res;
    }
    
    private void helper(List<String> res, String s, Set<String> dict, String path, int index) {
        if (index == s.length()) {
            res.add(path.substring(1)); //从1开始的子串。删去前面多余的空格
            return;
        }
        for (int i = index + 1; i <= s.length(); i++) {
            String word = s.substring(index, i);
            if (dict.contains(word)) { //和前面问题的区别处：如果在候选词中，执行helper()
                helper(res, s, dict, path + " "+  word, i);
            }
        }
    }
}