leetcode – Word Break II

和Word Break类似，向一个String切几刀，要求所以substring都在字典里，Word Break是能不能找到一种切法，这题是找出所有切法。
———————————————————————————————————————————————————————-
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].
———————————————————————————————————————————————————————-

首先就是上暴力DFS：

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> ret = new ArrayList<String>();
        if (s==null || s.length()==0) {return ret;}
        ArrayList<String> cur = new ArrayList<String>();
        dfs(s, 0, ret, cur, dict);
        return ret;
    }

    public void dfs(String s, int start, ArrayList<String> ret, ArrayList<String> cur, 
    Set<String> dict) {
        int n = s.length();

        for (int i=start; i<=n; i++) {
            String curWord = s.substring(start,i);
            if (dict.contains(curWord)) {
                cur.add(curWord);
                if (i==n) {
                    int m = cur.size();
                    String str = new String();
                    for(int j=0; j<m; j++) {
                        if (j!=0) {
                            str += " ";
                        }
                        str += cur.get(j);
                    }
                    ret.add(str);
                } else {
                    dfs(s, i, ret, cur, dict);
                }
                cur.remove(cur.size()-1);
            }
        }
    }
}

用Word Break的思路写了一个，每个长度把合理的word path记录下来，结果把heap跑暴了…

public class Solution {
    class Record {
        int start;
        int end;
        public Record(int start, int end) {
            this.start = start; this.end = end;
        }
        public Record(Record r) {
	    start = r.start;
	    end = r.end;
	}
	public String toString() {
            return "["+start+", "+end+"]";	
	}
    }

    ArrayList<ArrayList<Record>> deepCopy(ArrayList<ArrayList<Record>> paths) {
	if (paths==null) return null;
	int n = paths.size();
        ArrayList<ArrayList<Record>> ret = new ArrayList<ArrayList<Record>>(paths.size());
	for (int i=0; i<n; i++) {
		ArrayList<Record> path = paths.get(i);
		int m = path.size();
		ArrayList<Record> pathCopy = new ArrayList<Record>(m);
		for (int j=0; j<m; j++) {
		    pathCopy.add(new Record(path.get(j)));
		}
		ret.add(pathCopy);
	}
	return ret;
    }

    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> ret = new ArrayList<String>();
        if (s==null || s.length()==0) return ret;
        int n = s.length();
        Map<Integer, ArrayList<ArrayList<Record>>> dp = new HashMap<Integer, ArrayList<ArrayList<Record>>>();
        dp.put(0, new ArrayList<ArrayList<Record>>());
	dp.get(0).add(new ArrayList<Record>());
        for (int i=1; i<=n; i++) {
            for (int j=0; j<i; j++) {
                String cur = s.substring(j, i);
                ArrayList<ArrayList<Record>> paths = null;

                if (dp.containsKey(j) && dict.contains(cur)) {

                    paths = deepCopy(dp.get(j));

                    Record record = new Record(j, i);
                    for (ArrayList<Record> path:paths) {
                        path.add(record);
                    }
                }

                if (paths != null) {
                    if (!dp.containsKey(i)) {
                        dp.put(i, paths);
                    } else {
			dp.get(i).addAll(paths);
		    }
                }
            }
        }

        if (!dp.containsKey(n)) {
            return ret;
        }

        ArrayList<ArrayList<Record>> paths = dp.get(n);
        int numPaths = paths.size();
        for (int j=0; j<numPaths; j++) {
            ArrayList<Record> path = paths.get(j);
            String s2 = new String();
            int m = path.size();
            for (int i=0; i<m; i++) {
                if (i!=0) {s2+=" ";}
                int start = path.get(i).start;
                int end = path.get(i).end;
                s2+=s.substring(start, end);
            }
            ret.add(s2);
        }
        return ret;
    }
}

当然是会超时的，显然还是要上DP，但是Word Break那种一维DP显然不行，反正我想了2小时没想出来，还是要看答案了。

折腾了2天终于通过了，结果很坑爹。网上很多答案写得不好，非常误导。第一步dp的结果只用来判断一下从0到n-1的字符串能不能用字典里的词组成，不行直接返回(原来就是少了这一步…)，行的话就普通的DFS

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> ret = new ArrayList<String>();
        if (s==null || s.length()==0) return ret;
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for (int i=1; i<=n; i++) {
            if (dict.contains(s.substring(0, i))) {
                dp[i] = true;
                continue;
            }
            for (int j=0; j<i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        if (dp[n] == false) return ret; //DP的作用就这一行！！！
        StringBuilder cur = new StringBuilder();
        dfs(s, 0, cur, ret, dict);
        return ret;
    }

    public void dfs(String s, int start, StringBuilder cur, ArrayList<String> ret, Set<String> dict)  {
        int n = s.length();
        if (start >= n) {
            ret.add(new String(cur));
            return;
        }
        for (int i=start+1; i<=n; i++) {
            String sub = s.substring(start, i);
            if (dict.contains(sub)) {
                int oldLen = cur.length();
                if (oldLen!=0) cur.append(" ");
                cur.append(sub);
                dfs(s, i, cur, ret, dict);
                cur.delete(oldLen, cur.length());
            }
        }
    }
}