140 - Word Break II

Word Break II

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"].

Hide Tags

Dynamic Programming Backtracking

Hide Similar Problems

(M) Word Break

要构造所有结果，当然是 dfs。
但是…，码完了超时，还以为是要怎么剪枝，颠来倒去地折腾都不管用，始终是超时。
难道另有 DP 妙解么？怎么写也写不出来一个能罗列所有结果的状态方程，不应该啊？

看别人的帖子，好像是弄个辅助数组，记录从当前位置到尾巴这段是不是有解，
然后一边 dfs， 一边更新这个数组（递归返回后没有增加新结果），从而减少运行时间（跑的结果是 16 ms）。
明白这个意思，但是咋看都感觉不是题目所问的意图，差点儿意思。
直到比较帖子上的代码和我的代码跑超时的那个大集合的结果的时候，才留意到这个大集合根本是 unbreakable 的！

NND 还以为所有 case 都是可以 break 到底的，另有精妙算法呐，原来是整了一堆 unbreakable 的大坑啊！没意思。
好吧，这下倒也看清了此题的意图了：
它要问的是回溯，但是想要借用 139 - Word Break 的 DP  检测先判定字符串是不是 breakable 的，是的话才构造结果。
构造的时候，还可以进一步利用已经记录检测结果的 bool 数组，跳过 false的元素，只对 true 的处理并 dfs 就好了。
按照这个思路改完了一跑，4 ms！
回过头再看前面帖子里的方法，边做 dfs 边更新标志数组，难免有重复运算，不如 DP 一把检测完毕来的迅速，所以会慢一些。

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> rst;
        string buf;
        int sz = wordDict.size(), ll = s.length();

        //reuse DP in Word Break I to check if string is breakable
        bool cutable[ll+1];
        cutable[0]=true;
        for(int se=1; se<=ll; ++se)
        {
            cutable[se] = false;
            for(int ss=se-1; ss>=0; --ss)
                if(cutable[ss] && wordDict.end()!=wordDict.find(s.substr(ss, se-ss)))
                {
                    cutable[se] = true;
                    break;
                }
        }

        //dfs to generate result if breakable
        if(cutable[ll] && ll && sz)
            dfs(s, ll, wordDict, cutable, 0, 0, buf, rst);
        return rst;
    }
   
    void dfs(string& s, int len, unordered_set<string>& wd,
            bool cutable[], int ss/*substring start*/,
                int blen, string& buf, vector<string>& rst)
    {
        for(int se=ss; se<=len; ++se)
        {
            if(cutable[se+1])
            {
                string str = s.substr(ss, se-ss+1);
                int ls = se-ss+1;
                if(wd.end()!=wd.find(str))
                {
                    buf += str;
                   
                    if(len==se+1)
                        rst.push_back(buf);
                    else
                    {
                        buf += " ", ls++;
                        dfs(s, len, wd, cutable, se+1, blen+ls, buf, rst);
                    }
                   
                    buf.erase(blen, ls);
                }
            }
           
        }
    }
};
4 ms.