140. 单词拆分 II

140. 单词拆分 II

回溯

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set(wordDict.begin(), wordDict.end());
        vector<string> ret;
        vector<string> st;
        backTrack(s, s.size(), 0, set, ret, st);
        return ret;
    }
private:
    void backTrack(string& s, int sz, int start, unordered_set<string>& set, vector<string>& ret, vector<string>& st)
    {
        if(start == sz)
        {
            string r;
            for(auto& str : st)
                r += str + " ";
            r.pop_back();
            ret.push_back(r);
            return;
        }
        int end = start;
        while(end < sz)
        {
            auto cur = s.substr(start, end - start + 1);
            if(set.count(cur))
            {
                st.push_back(cur);
                backTrack(s, sz, end + 1, set, ret, st);
                st.pop_back();
            }
            ++end;
        }
    }
};

对回溯过程中进行记忆优化

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        map = vector<vector<string>>(s.size() + 1);
        set = unordered_set<string>(wordDict.begin(), wordDict.end());
        backTrack(s, s.size(), 0);
        return map[0];
    }
private:
    unordered_set<string> set;
    vector<vector<string>> map; // 对于同一起始点的，使用这个map来记录，因为同一起始点开始的字符串的子一定一样，不用重新计算。
    void backTrack(string& s, int sz, int index)
    {
        if(!map[index].empty()) // 走过的就不用再走了
            return;
        if(index == sz) // 走到最后了，加入个空字符串，为了后面可以添加进去而不至于当作没走过。
        {
            map[index].push_back(""); 
            return;
        }
        for(int i = index; i < sz; ++i)
        {
            auto word = s.substr(index, i - index + 1);
            if(set.count(word))
            {
                backTrack(s, sz, i + 1); // 回溯，先把后面的计算完再用前面的加。
                for(auto& str : map[i + 1])
                    map[index].push_back(str.empty() ? word : word + " " + str);
            }
        }
    }
};