Word Break II -- LeetCode

 
這道題目要求跟Word Break比較類似，不過返回的結果不僅要知道能不能break，如果可以還要返回所有合法結果。一般來說這種要求會讓動態規劃的效果減弱很多，因為我們要在過程中記錄下所有的合法結果，中間的操作會使得算法的復雜度不再是動態規劃的兩層循環，因為每次迭代中還需要不是constant的操作，最終復雜度會主要取決於結果的數量，而且還會占用大量的空間，因為不僅要保存最終結果，包括中間的合法結果也要一一保存，否則後面需要歷史信息會取不到。所以這道題目我們介紹兩種方法，一種是直接brute force用遞歸解，另一種是跟Word Break思路類似的動態規劃。
對於brute force解法，代碼比較簡單，每次維護一個當前結果集，然後遍歷剩下的所有子串，如果子串在字典中出現，則保存一下結果，並放入下一層遞歸剩下的字符。思路接近於我們在N-Queens這些NP問題中經常用到的套路。代碼如下：

public ArrayList wordBreak(String s, Set dict) {
    ArrayList res = new ArrayList();
    if(s==null || s.length()==0)
        return res;
    helper(s,dict,0,,res);
    return res;
}
private void helper(String s, Set dict, int start, String item, ArrayList res)
{
    if(start>=s.length())
    {
        res.add(item);
        return;
    }
    StringBuilder str = new StringBuilder();
    for(int i=start;i0?(item+ +str.toString()):str.toString();
            helper(s,dict,i+1,newItem,res);
        }
    }
}

接下來我們列出動態規劃的解法，遞推式跟Word Break是一樣的，只是現在不只要保存true或者false，還需要保存true的時候所有合法的組合，以便在未來需要的時候可以得到。不過為了實現這點，代碼量就增大很多，需要一個數據結構來進行存儲，同時空間復雜度變得非常高，因為所有中間組合都要一直保存。時間上還是有提高的，就是當我們需要前面到某一個元素前的所有合法組合時，我們不需要重新計算了。不過最終復雜度還是主要取決於結果的數量。代碼如下：

class Interval {
    int start;
    int end;
    public Interval(int start, int end) {
        this.start = start; this.end = end;
    }
    public Interval(Interval i) {
        start = i.start;
        end = i.end;
 }
}
ArrayList> deepCopy(ArrayList> paths) {
    if (paths==null) return null;
    ArrayList> res = new ArrayList>(paths.size());
    for (int i=0; i path = paths.get(i);
     ArrayList copy = new ArrayList(path.size());
        for (int j=0; j wordBreak(String s, Set dict) {
    ArrayList res = new ArrayList();
    if (s==null || s.length()==0) return res;
    Map>> dp = new HashMap>>();
    dp.put(0, new ArrayList>());
    dp.get(0).add(new ArrayList());
    for (int i=1; i<=s.length(); i++) {
        for (int j=0; j> paths = null;
            if (dp.containsKey(j) && dict.contains(cur)) {
                paths = deepCopy(dp.get(j));
                Interval interval = new Interval(j, i);
                for (ArrayList path:paths) {
                    path.add(interval);
                }
            }
            if (paths != null) {
                if (!dp.containsKey(i)) {
                    dp.put(i, paths);
                } 
                else {
              dp.get(i).addAll(paths);
             }
            }
        }
    }
    if (!dp.containsKey(s.length())) {
        return res;
    }
    ArrayList> paths = dp.get(s.length());
    for (int j=0; j path = paths.get(j);
        StringBuilder str = new StringBuilder();
        for (int i=0; i可以看出，用動態規劃的代碼復雜度要遠遠高於brute
 force的解法，而且本質來說並沒有很大的提高，甚至空間上還是一個暴漲的情況。所以這道題來說並不是一定要用動態規劃，有一個朋友在面Amazon時遇到這道題，面試官並沒有要求動態規劃，用brute force即可，不過兩種方法時間上和空間上的優劣還是想清楚比較好，面試官可能想聽聽理解。實現的話可能主要是遞歸解法。

還有一點需要指出的是，上面的兩個代碼放到LeetCode中都會超時，原因是LeetCode中有一個非常tricky的測試case，其實是不能break的，但是又很長，出現大量的記錄和回溯，因此一般通過這個的解法是把Word
 Break先跑一遍，判斷是不是能break，如果可以再跑上面的代碼。這樣做法其實比較傻，但是為了過這個只能這樣了，這一點我覺得LeetCode沒必要把超時設得這麼嚴格，實際意義不大，只是把AC率給拉了下來哈。