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

用到了动态规划和字典查询，f(n)表示从从0到第n个字符有哪些解，则f(n) = (字母(0到n)如果在字典中，则并入f(0)的解) + (字母(1到n)如果在字典中，则并入f(1)的解).... (字母(n-1到n)如果在字典中，则并入f(n-1)的解),最终输出f(n)

class Solution {
public:
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param dic string字符串vector 
 * @return string字符串vector
 */
vector<string> wordDiv(string s, vector<string>& dic) {
    map<string, int> dictionary;
    int i = 1;
    
    // 使用map记录已有单词便于查询
    for (auto it = dic.begin(); it != dic.end(); it ++) {
        dictionary[*it] = i;
        i ++;
    }
    int size = s.size();
    
    // 使用vector<int>记录解，也可以用string。
    // 所以answer[i] = vector<vector<int>> 也就是到第i个字母为止的解的合集。
    vector<vector<vector<int>>> answer(size);
    for(int i = 0; i < size; i++) {
        vector<vector<int>>& thisAnswer = answer[i];
        for (int j = 0; j <= i; j++) {
            // 如果第j-i字母在字典中，则把这个解，并上 preAnswers = answer[j - 1]的解，添加到thisAnswer中去
            string testStr = s.substr(j, i-j + 1);
            if (dictionary[testStr]) {
                if (j == 0) {
                    thisAnswer.push_back({dictionary[testStr]});
                } else {
                    vector<vector<int>>& preAnswers = answer[j - 1];
                    for (auto it = preAnswers.begin(); it != preAnswers.end(); it ++) {
                        vector<int> newVec(it->begin(), it->end());
                        newVec.push_back(dictionary[testStr]);
                        thisAnswer.push_back(newVec);
                    }
                }
                 
            }
        }
    }
    
    // 将结果转成vector<string>输出
    vector<string> answerStrs;
    for (auto it = answer[size - 1].begin(); it < answer[size - 1].end(); it++) {
        string str = "";
        for (auto it1= it->begin(); it1 < it->end(); it1++) {
            int t = *it1;
            if (str != "") {
                str += " ";
            }
            str += dic[t - 1];
        }
        answerStrs.push_back(str);
    }
    sort(answerStrs.begin(), answerStrs.end());
    return answerStrs;
}
};