[C++]leetcode 单词拆分II

题目描述：

思路：

本来想直接在【单词拆分】里加一个for循环解决问题，思路是定义一个数组，用来记录能到达字符串s位置i的所有可能的字符串，那么往下查找时，在找到下一个可行位置时就把上一个位置里的字符串通过for循环加进来，最终返回数组最后一个元素就行了，代码如下：

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int n=s.size(),n_word,tmp,k,n_res;
        vector<int> m(n+1);
        vector<vector<string>> res(n+1);
        m[0]=1;
        res[0]={""};
        n_word=wordDict.size();
        for(int i=1;i<n+1;i++) {
            for(int j=0;j<n_word;j++) {
                tmp=wordDict[j].size();
                if (i-tmp>=0 && m[i-tmp]==1 && s.substr(i-tmp,tmp)==wordDict[j]) {
                    m[i]=1;
                    n_res=res[i-tmp].size();
                    for(k=0;k<n_res;k++) {
                        if (i-tmp==0)
                            res[i].push_back(wordDict[j]);
                        else
                            res[i].push_back(res[i-tmp][k]+" "+wordDict[j]);
                    }
                }
            }
        }
        return res[n];
    }
};

 但是超时了，在网上看了其它的解法，用了dp+dfs，先dp判断能不能被分割，再dfs搜索所有可行解，dfs搜索的思路是：假如字符串长度为n,找到了字符串s的[0:i]段在字典内，就递归继续查找[i,n]段，如果最终能到达n位置，就是一个解，加进数组中，其实比较简单，代码如下：

class Solution {
private:
    vector<string> res;
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int n=s.size(),n_word,tmp;
        vector<int> m(n+1);
        m[0]=1;
        n_word=wordDict.size();
        for(int i=1;i<n+1;i++) {
            for(int j=0;j<n_word;j++) {
                tmp=wordDict[j].size();
                if (i-tmp>=0 && m[i-tmp]==1 && s.substr(i-tmp,tmp)==wordDict[j])
                    m[i]=1;
            }
        }
        if (!m[n])
            return {""};
        dfs(s,wordDict,0,n,"");
        return res;
    }
    void dfs(string s,vector<string>& words,int st,int n,string tmp) {
        int k=tmp.size();
        if (st==n) {
            res.push_back(tmp.substr(0,k-1));
            return;
        }
        for(int i=st+1;i<n+1;i++) {
            if (find(words.begin(),words.end(),s.substr(st,i-st))!=words.end())
                dfs(s,words,i,n,tmp+s.substr(st,i-st)+" ");
        }
        return;
    }
};