[LeetCode] 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

 

 

方法一：

DFS，

start已知，当start超过str长度时，说明全部字符串都能找到了。。

小数据可过，大数据时超时

class Solution {
    private:
        // DFS
        void wordBreak(string s, int start, unordered_set<string> & dict)
        {
            size_t size =  s.size();
            if(size == 0)
                return;
            if(start >= size)
            {
                string tmpStr;
                for(int i = 0; i < m_str.size(); i++)
                {
                    if(i == m_str.size() - 1)
                        tmpStr += m_str[i];
                    else
                        tmpStr += m_str[i] + " ";
                }
                m_strs.push_back(tmpStr);
            }

            for( int i = start; i <size; i++)
            {
                string str = s.substr(start, i-start+1);
                if(dict.find(str) != dict.end())
                {
                    m_str.push_back(str);
                    wordBreak(s,i+1, dict);
                    m_str.pop_back();
                }

            }
        }

    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            m_str.clear();
            m_strs.clear();

            wordBreak(s,0, wordDict);

            return m_strs;
        }
   private:
        vector<string> m_str;
        vector<string> m_strs;
};

方法二：

长度为 n 的字符串有 n+1 个隔板

基于dp之后，使用 vector<vector<string> > map 来保存当前的划分，

map[i] = {map[j]中原有的划分字符串} + s[j+1, i]，if s[j+1, i] 存在于字典中，

具例子，

s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

map[7] = {"cat sand", "cats and""}

map[10] = {"cat sand dog", "cats and dog"}, dog 在字典中。

但是 Status: Memory Limit Exceeded，头一次遇到这个错误。

        vector<string> wordBreak2(string s, set<string> &dict) {
            vector<bool> f(s.size() + 1, false);
            vector<string> tmpStrVec;
            vector<vector<string> > map(s.size()+ 1, tmpStrVec);
            f[0] = true;
            for (int i = 1; i <= s.size(); ++i)
            {
                for (int j = i - 1; j >= 0; --j)
                {
                    string subStr = s.substr(j, i-j);
                    if (f[j] && dict.find(subStr) != dict.end())
                    {
                        f[i] = true;
                        vector<string> strVec = map[j];
                        if(strVec.size() == 0)
                        {
                            strVec.push_back(subStr);
                            map[i] = strVec;
                        }
                        else
                        {
                            for(int k = 0; k < strVec.size(); k++)
                            {
                                strVec[k] += " " + subStr ;
                                map[i].push_back(strVec[k]);
                            }
                        }
                    }
                }
            }
            return map[s.size()];

方法三： 这题不能直接DFS，否则会超时，联想到上一题，可以跟上题一样先动态规划，判断能否被break，如果s不能被break，那么也没有DFS的必要

class Solution {
    public:
        void breakWord(vector<string> &res, string &s, unordered_set<string> &dict, string str, int start, vector<bool> &f) {

            if(f[start] == false) return ;
            if(start >= s.size())
                res.push_back(str);


            for(int i = start; i <s.size(); i++)
            {
                string subStr = s.substr(start, i-start + 1);
               // cout <<"i 	" <<i << "	j	" << i-start<<"	"<<subStr << endl;
                if(dict.count(subStr))
                {
                    if(str.empty())
                        breakWord(res,s,dict, subStr, i+1,f);
                    else
                        breakWord(res,s,dict, str+" "+subStr, i+1,f);
                }

            }
        }

        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            vector<bool> f(s.size() + 1, false);
            f[0] = true;
            for (int i = 1; i <= s.size(); ++i) {
                for (int j = i - 1; j >= 0; --j) {
                    if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                        f[i] = true;
                        break;
                    }
                }
            }

            vector<string> res;
            if (f[s.size()])
                breakWord(res, s, dict, "", 0, f);
            return res;
        }
};