题解 | #单词拆分(二)#

采用动态规划算法

        // write code here
    vector<vector<string>> dp(s.length()+1, vector<string>());
    set<string> wordDict;
    for(auto d : dic){
        wordDict.insert(d);
    }
    int len = s.length();
    dp[0] = {""};
    for (int i = 1; i <= len; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (dp[j].size() == 0) continue;
            string suffix = s.substr(j, i-j);
            if (wordDict.find(suffix) != wordDict.end() && dp[j].size()) { //若发现从j->i这一段字符串存在于set中，并且dp[j]有句子，那么就可以对dp[j]中的每个句子新增这一字符串得到此处的dp[i]
                for(auto d : dp[j]){
                    dp[i].push_back(d + (j == 0 ? "" : " ") + suffix);
                }
            }
        }
    }
    sort(dp[s.length()].begin(), dp[s.length()].end());
    return dp[s.length()];
    }