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"] . 동적 기획
우선, 문자열을 분할할 수 있는지, 동적 기획으로 해결할 수 있는지를 결정한다.
모든 실행 가능한 결과를 출력해야 할 때, 비망록을 사용하여 모든 단계의 선구 결점을 기록해야 한다.즉, 각 단어의 이전 단어의 위치를 기록합니다.이전 단어가 유일하지 않을 수 있기 때문에, 가장 큰 개수는 n(총 n개의 위치)이다.
주: i의 위치에 대해 s[0...i]의 구분 가능 여부를 판단한다. 만약에 이 단어 자체가 사전에 있다면 그의 전구 index는 -1이고, 만약에 s[j...i-1]가 합법적인 단어이고 s[0...j-1]도 합법적인 단어라면 그의 전구 index는 j-1이어야 한다. 이와 같이 각 위치의 전구 노드의 개수는 n까지이다.상술한 바와 같이 -1이라는 음수가 나타났기 때문에 우리는 s의 하표를 1부터 정의한다.다음 "i자는"s[i-1]를 나타냅니다.따라서 2차원 그룹 비망록 tbl[n+1][n]을 정의합니다. 그 중에서 tbl[i]는 i자 문자의 모든 전구 결점의 index의 집합을 나타냅니다.
코드:

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict)
    {
        vector<string> ret;
        if(s.empty())
            return ret;
        int len = s.length();
        vector<vector<int> > tbl(len + 1, vector<int>());
        GenerageTable(s, dict, tbl);
        string path;
        dfs(s, tbl, ret, path, len);
        return ret;
    }
    // tbl   i ， tbl[i] ， 
    void GenerageTable(const string& s, unordered_set<string>& dict,
                       vector<vector<int> >& tbl)
    {
        int len = s.size();
        vector<bool> flag(len + 1, false);
        flag[0] = true;
        for (size_t i = 1; i <= len; ++i) {
            for (size_t j = 0; j < i; ++j) {
                if(flag[j] && dict.count(s.substr(j, i - j)) != 0)
                {
                    tbl[i].push_back(j);
                    flag[i] = true;
                }
            }
        }
    }
    // ret 
    void dfs(const string& s, vector<vector<int> >& tbl, vector<string>& ret, string& path, int step)
    {
        if(step == 0)
            ret.push_back(path);
        if (tbl[step].size()) {
            for(size_t i = 0; i < tbl[step].size(); ++i)// step 
            {
                string tmp = path;
                if(!path.empty())
                    path = ' ' + path;//save the break word using space to seperate it.
                path = s.substr(tbl[step][i], step - tbl[step][i]) + path;
                dfs(s, tbl, ret, path, tbl[step][i]);
                path = tmp;// path， 
            }
        }
    }
};