Leetcode 140 Word Break II

Leetcode 140 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"].

Diffculty
Hard

Similar Problems
[LeetCode 79] Word Search

Analysis

这题需要利用在 DFS 过程中，进行 bookkeeping，也就是 DP 数组做标记，再加上剪枝的方法，如果某个点 i 在之前的搜索中没有得到结果，那么以后遇到它就不进行搜索了。 这里加上一个 possible 数组，如同 WordBreak I 里面的 DP 数组一样，用于记录区间能否 break 的可能性，possible[i] = true 表示 [i, n] 这个区间上有解，n 为 s 的长度，如果某个区间之前被判定了无解，下次循环时就会跳过这个区间，从而大大减少了运行时间。

Solutions

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        string result;
        vector<string> sol;
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        int len = s.size();
        vector<bool> possible(len + 1, true); // to record the search which has been executed once
        GetAllSolution(s, dict, 0, len, result, sol, possible);
        return sol;
    }
    void GetAllSolution(const string& s, const unordered_set<string> &dict, int start, int len, string& result, vector<string>& sol, vector<bool>& possible) {
        if (start == len) {
            sol.push_back(result.substr(0, result.size() - 1)); // eliminate the last space
            return;
        }
        for (int i = start; i < len; ++i) {
            string piece = s.substr(start, i - start + 1);
            if (dict.find(piece) != dict.end() && possible[i + 1])  { // 如果条件一直无法满足导致无法执行下面的代码，那么就会造成 sol.size() == beforeChange，这样，递归回去的时候，就可以把 possible[i + 1] 设置成 false。这样就可以剪枝了。
                result.append(piece).append(" ");
                int beforeChange = sol.size();
                GetAllSolution(s, dict, i + 1, len, result, sol, possible);
                if(sol.size() == beforeChange) // if no solution, set the possible to false
                    possible[i + 1] = false;
                result.resize(result.size() - piece.size() - 1);
            }
        }
    }
};