常规无优化解题思路

void dfs(s,u,now){//u为新单词的开头
    if(u==n) 记录答案 结束;
    for(int j = u; j < n; j++){ //j为新单词的截止位置
        if(s[u~j]在词典中存在) dfs(s,j+1,now+s[u~j]+' ');      ①
    }
}

但此方法会超时 原因就是例如 s = "aaaaaab" 词典="a","aa","aaa"
很明显可以看出s由于最后的b是无法利用词典中的单词拼出的

复杂度之所以高 是因为无法预判之后的数能否被拼出 且存在大量的重复计算
如u = 0时 会执行dfs(1) dfs(2) dfs(3)
而dfs(1) 会执行dfs(2) dfs(3) dfs(4) …
因此存在着大量的重复计算

因此出现一个新思路
假如u~j在词典中存在 若能提前预知j之后的字符串能否由词典拼出 则会大大减少无用的计算
也就是需要预处理一个数组 f[j]表示s[j~n-1]能否由词典中的单词拼出(139.单词拆分) 这样就可以及早剪枝

优化后的解题思路

void dfs(s,u,now){//u为新单词的开头
    if(u==n) 记录答案 结束;
    for(int j = u; j < n; j++){ //j为新单词的截止位置
        if(s[u~j]存在&&f[j+1]) dfs(s,j+1,now+s[u~j]+' ');  //当u~j存在 且 j之后的可以由词典拼出 才继续搜索
    }
}

完整代码如下

    vector<bool> f;//f[i]表示s[i~n-1]能否利用词典拼出
    unordered_set<string> hash;
    vector<string> ans;
    int n;
    void dfs(string &s, int u, string now){//从u开始搜索 u为新单词的开头 当前的句子为now
        if(u == s.size()){
            now.pop_back();//去除尾部空格
            ans.push_back(now);
            return;
        }
        for(int j = u; j < n; j++){//j为新单词结尾 当u~j存在 且j之后的可以被拼出时 才会继续搜索
            if(f[j+1]&&hash.count(s.substr(u,j-u+1))) dfs(s,j+1,now+s.substr(u,j-u+1)+" ");
        }
    } 
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size(), f.resize(n+1);
        for(auto w : wordDict) hash.insert(w);
        f[n] = true;
        for(int i = n-1; ~i; i--){
            for(int j = i; j < n; j++){
                if(hash.count(s.substr(i,j-i+1))&&f[j+1]){//若 i~j 在字典中存在 且 j之后的能拼出 则i之后的也能拼出
                    f[i] = true;
                    break;
                } 
            }
        }
        dfs(s,0,"");
        return ans;
    }