140. 单词拆分 II

这道题思路不难想，但是代码却改了好几次才通过，最主要的问题是会出现超时间/超内存
第一种方式：
利用动态规划—超时间限制，因为有很多没有利用到的状态也被计算了，这些状态也都被计算了下来

class Solution {
public:
   vector<string> wordBreak(string s, vector<string>& wordDict) {
       int n = s.size();
       vector<vector<vector<string>>> dp(n, vector<vector<string>>(n));
       for(int len = 1; len <= n; len++)
       {
           for(int l = 0; l < n; l++)
           {
               int r = l + len - 1;
               if(r >= n) break;
               string sub = s.substr(l, r - l + 1);
               if(find(wordDict.begin(), wordDict.end(), sub) != wordDict.end())
               {
                   dp[l][r].push_back(sub);
               }
               for(int k = l; k < r; k++)
               {
                   if(dp[l][k].size() && dp[k + 1][r].size())
                   {
                       for(auto x: dp[l][k])
                           for(auto y: dp[k+1][r])
                           {
                               string tmp = x + " " + y;
                               dp[l][r].push_back(tmp);
                           }
                   }
               }
           }
       }
       vector<string> res;
       sort(dp[0][n - 1].begin(), dp[0][n - 1].end());
       for(auto x: dp[0][n - 1])
       {
           if(!res.size() || x != res.back())
               res.push_back(x);
       }
       return res;
   }
};

dp—超内存限制 原因是到最后了才发现最后面的拼不起来啊，那个恨，前面的都浪费了

class Solution {
public:
   vector<string> wordBreak(string s, vector<string>& wordDict) {
       int n = s.size();
       vector<vector<string>> dp(n);
       for(int i = 0; i < s.size(); i++)
       {
           string sub = s.substr(0, i - 0 + 1);
           if(find(wordDict.begin(), wordDict.end(), sub) != wordDict.end())
           {
               dp[i].push_back(sub);
           }
           for(int j = i; j > 0; j--)
           {
               string sub = s.substr(j, i - j + 1);//[j, i]
               if(find(wordDict.begin(), wordDict.end(), sub) != wordDict.end() && dp[j - 1].size())
               {
                   for(auto x: dp[j - 1])
                   {
                       dp[i].push_back(x + " " + sub);
                   }
               }
           }
       }
       return dp[n - 1];
   }
};

dfs—先扫一次到最后看看能不能拼起来，如果能拼起来再拼起来，并且可以去利用set加快搜索速度

class Solution {
   string s;
   set<string> wordDict;
   map<int, vector<string>> mp;
   vector<int> v;
   void dfs(int start)
   {
       if(start == s.size())
       {
           v[start] = 1;
           mp[start] = {""};
           return;
       }
       if(v[start] != -1)//说明已经访问过了
       {
           return;
       }
       vector<string> res;
       for(int k = start; k < s.size(); k++)
       {
           string sub = s.substr(start, k - start + 1);
           if(wordDict.count(sub))
           {
               dfs(k + 1);
               if(v[k+1] == 0) continue;
               for(auto x: mp[k+1])
               {
                   if(x.size())
                       res.push_back(sub + " " + x);
                   else
                       res.push_back(sub);
               }
           }
       }
       if(res.size())
       {
           v[start] = 1;
           mp[start] = res;
       }
       else
       {
           v[start] = 0;
       }
       return;
   }
public:
   vector<string> wordBreak(string _s, vector<string>& _wordDict) {
       s = _s;
       for(auto x:_wordDict)
           wordDict.insert(x);
       v = vector<int>(s.size() + 1, -1);//-1没有搜索， 0 不行 1可以
       dfs(0);
       vector<string> tmp = mp[0];
       if(tmp.size())
           return tmp;
       else
           return vector<string>();
   }
};

第二次写题

class Solution {
    vector<vector<string>> res;//这里相当于保存记录，防止多次调用
    vector<int> mask;//这里相当于记录这个idx开始的是否被访问过
    set<string> st;
    void dfs(string s, int idx)
    {
        if(idx == s.size()) return;
        for(int i = idx; i < s.size(); i++)
        {
            string str = s.substr(idx, i - idx + 1);
            if(st.find(str) != st.end())
            {
                //这里有意思，这里可以实现先后面的
                if(mask[i + 1] == -1) dfs(s, i + 1);
                //然后再回来这里进行拼接
                for(auto x: res[i + 1])
                {
                    //这里有两种情况，因为如果是最后就不用加' '
                    if(x != "")
                        res[idx].push_back(str + ' ' + x);
                    else
                        res[idx].push_back(str);
                }
            }
        }
        //做一下标记，这个idx已经被找过了
        mask[idx] = 1;
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        if(!s.size()) return vector<string>();
        res.resize(s.size() + 1);
        res[s.size()]= {""};
        mask.resize(s.size() + 1, -1);
        mask[s.size()] = 1;
        for(auto x: wordDict)
        {
            if(st.find(x) == st.end())
                st.insert(x);
        }
        //下面这里是想看有没有在s出现的字母没有出现在wordDict里面 
        //如果在s出现在wordDict没有出现，那肯定匹配不上
        set<char> worddic;
        set<char> word;
        for(auto x: s)
        {
            if(word.find(x) == word.end())
                word.insert(x);
        }
        for(auto x: st)
        {
            for(auto c: x)
            {
                if(worddic.find(c) == worddic.end())
                    worddic.insert(c);
            }
        }
        for(auto x: word)
        {
            if(worddic.find(x) == worddic.end())
                return vector<string>();
        } 
        //dfs
        dfs(s, 0);
        //返回 res是二维的，所以这里返回的是第一个
        return res[0];
    }
};

第三次写题

class Solution {
    vector<vector<string>> res;
    vector<bool> mask;
    set<string> dict;
    void dfs(string s, int idx)
    {
        if(idx >= s.size()) return;
        if(mask[idx] == false) return;
        mask[idx] = false;
        for(int i = idx; i < s.size(); i++)
        {
            string str = s.substr(idx, i - idx + 1);
            if(dict.find(str) == dict.end()) continue;
            dfs(s, i + 1);
            for(auto x: res[i + 1])
            {
                string ns = str + (x==""? "":' '+x); 
                res[idx].push_back(ns);
            }
        }
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        if(!s.size()) return vector<string>();
        res.resize(s.size() + 1);
        mask = vector<bool>(s.size() + 1, true);
        res[s.size()] = {""};
        mask[s.size()] = false;
        for(auto w: wordDict)
        {
            if(dict.find(w) == dict.end())
                dict.insert(w);
        }
        dfs(s, 0);
        return res[0];
    }
};

需要注意的是加了一段利用char来先筛选的，会让使用的内存数量减小，从17.2M->13.2M

class Solution {
    vector<vector<string>> res;
    vector<bool> mask;
    set<string> dict;
    void dfs(string s, int idx)
    {
        if(idx >= s.size()) return;
        if(mask[idx] == false) return;
        mask[idx] = false;
        for(int i = idx; i < s.size(); i++)
        {
            string str = s.substr(idx, i - idx + 1);
            if(dict.find(str) == dict.end()) continue;
            dfs(s, i + 1);
            for(auto x: res[i + 1])
            {
                string ns = str + (x==""? "":' '+x); 
                res[idx].push_back(ns);
            }
        }
    }

public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        if(!s.size()) return vector<string>();
        res.resize(s.size() + 1);
        mask = vector<bool>(s.size() + 1, true);
        res[s.size()] = {""};
        mask[s.size()] = false;
        for(auto w: wordDict)
        {
            if(dict.find(w) == dict.end())
                dict.insert(w);
        }
        //和上面的比，加了这一段
        set<char> worddic;
        set<char> word;
        for(auto x: s)
        {
            if(word.find(x) == word.end())
                word.insert(x);
        }
        for(auto x: dict)
        {
            for(auto c: x)
            {
                if(worddic.find(c) == worddic.end())
                    worddic.insert(c);
            }
        }
        for(auto x: word)
        {
            if(worddic.find(x) == worddic.end())
                return vector<string>();
        } 
        //
        dfs(s, 0);
        return res[0];
    }
};