139 - Word Break

Word Break

Given a string s and a dictionary of words dict, 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".

Hide Tags

Dynamic Programming

Hide Similar Problems

(M) Palindrome Partitioning (H) Word Break II

先没想到 DP，弄了个 Q，把所有切出来的单词能在字典里找到的切口位置放到 Q 里，
然后逐个取出来继续下一轮，直到最后，切最后一个字母还能找到就是true。
逻辑上是合理的，但是复杂度太高，反复生成大量子串并逐个检查，最终 TLE。

所以还得是 DP。
延续之前 132 - Palindrome Partitioning II 的思路，用一个一维数组 check[] 存储子串 s[0, se) 是否能拆分的结果，
以 (ss, se) 分别为起点 (substr_start)，终点 (substr_end) 取出一个子串 s[ss, se)（包含 s[ss]，不包含 ss[se]），
如果能在字典里找到该子串，则 check[se] 的结果，依赖于 ss 之前一个字符对应的 check[] 里保存的结果，
注意因为 check[0] 对应的是空子串的结果，所以 ss-1 对应的结果是存在 check[ss] 下的，
如果它是true，则 check[se] 是true。

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int len = s.length();
        if(!len)
            return false;

        bool check[len+1];                  //stores judgement if s[0, se) is breakable
        check[0]=true;                      //set true for empty substring
        for(int se=1; se<=len; ++se)
        {
            check[se] = false;              //initialization as false
            //for(int ss=0; ss<se; ++ss)    //slower about 8 ms when start from beginning.
            for(int ss=se-1; ss>=0; --ss)
            {
                //get previous judgement in check[ss-1],
                //if substr s[ss, se) is found in dictionary,
                //then whether substr s[0, se) is breakable depends on previous judgement.
                if(check[ss] && wordDict.end()!=wordDict.find(s.substr(ss, se-ss)))
                {
                    check[se] = true;
                    break;                  //unnecessary to continue once find a true
                }
            }
        }
        return check[len];
    }
   
    bool wordBreak_q_timeout(string s, unordered_set<string>& wordDict) {
        int len=s.length(), bgn=0, pos=0;
        if(!len)
            return false;
           
        queue<int> q;
        q.push(pos);
        while(q.size())
        {
            bgn=q.front();
            pos=bgn;
            q.pop();

            while(pos<len)
            {
                while(pos<len && wordDict.end()==wordDict.find(s.substr(bgn, pos-bgn+1)))
                    pos++;

                if(len-1==pos)
                    return true;

                if(len-1>pos)
                    q.push(pos+1), pos++;
            }
        }
        return false;
    }
};
0 ms， TLE.