c++动态规划加递归参考题解

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& dict) {
        vector<string> result;
        if (s.empty() || dict.empty()) return result;
        int l = s.length();
        vector<bool> flag(l + 1, false);
        flag[0] = true;
        // link[i][j]=index 表示s中的 [index, i)是一个单词
        vector<vector<int>> link(l + 1);
        //动态规划记录所有单词链
        for (int i = 1; i <= l; ++i)
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (flag[j] && dict.find(s.substr(j, i - j)) != dict.end())
                {
                    link[i].push_back(j);
                    flag[i] = true;
                }
            }
        }
        //flag[l]为false表示不能成功拆分s
        if (!flag[l]) return result;
        result = { "" };
        return GenerateString(result, link, l, s);
    }

    //传引用是为了剩内存和时间
    vector<string>& GenerateString(vector<string>& strs, vector<vector<int>>& link, int index, string& s)
    {
        if (index == 0) return strs;
        int branch = link[index].size();
        if (branch == 1)
        {
            for (string& str : strs)
            {
                string tmp = s.substr(link[index][0], index-link[index][0]);
                if(index !=s.length())
                    tmp.append(" ");
                str = tmp.append(str);
            }
            return GenerateString(strs, link, link[index][0], s);
        }
        else
        {
            vector<vector<string>> tree(branch, strs);
            strs.clear();
            for (int i = 0; i < branch; ++i)
            {
                for (string& str : tree[i])
                {
                    string tmp = s.substr(link[index][i], index - link[index][i]);
                    if (index != s.length())
                        tmp.append(" ");
                    str = tmp.append(str);
                }
                vector<string>& subtree = GenerateString(tree[i], link, link[index][i], s);
                strs.insert(strs.end(), subtree.begin(), subtree.end());
            }
            return strs;
        }
    }
};