140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

Solution

Approach 1: backtracking -- add a cache to remember what's already calculated.

Code (Python)

Approach 1:

    def wordBreak(self, s, wordDict):
        words = set(wordDict)
        return list(map(lambda lst: ' '.join(lst), self._break_words(s, words, {})))
    
    def _break_words(self, string, words, cache):
        if string in cache:
            return cache[string]
        if not string or not words:
            return []
        result = []
        for i in range(0, len(string)):
            if string[:i+1] in words:
                if i + 1 == len(string): # base case
                    result.append([string])
                else:
                    for partial_result in self._break_words(string[i+1:], words, cache):
                        result.append([string[:i+1]] + partial_result)
        cache[string] = result
        return result

Code (C++)

Approach 1:

class Solution {
private:
    unordered_set<string> words;
    unordered_map<string,vector<string>> umap;
    vector<string> doWordBreak(string s, int head) {
        vector<string> res;
        string key = s.substr(head);
        if (umap.find(key) != umap.end())
            return umap[key];
        for (int tail = head; tail < s.size(); ++tail)
        {
            string tmpWord = s.substr(head, tail - head + 1);
            if (words.find(tmpWord) != words.end())
            {
                if (tail == s.size() - 1)
                {
                    res.push_back(tmpWord);
                }
                else
                {
                    vector<string> tmpRes = doWordBreak(s, tail+1);
                    for (int i = 0; i < tmpRes.size(); ++i)
                    {
                        res.push_back(tmpWord + ' ' + tmpRes[i]);
                    }
                }
            }
        }
        umap[key] = res;
        return res;
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for (int i = 0; i < wordDict.size(); ++i)
        {
            words.insert(wordDict[i]);
        }
        return doWordBreak(s, 0);
    }
};

// Time Limit Exceeded.
class Solution {
private:
    unordered_set<string> words;
    vector<string> res;
    void doWordBreak(string s, int head, vector<string>& buf) {
        if (head == s.size())
        {
            ostringstream oss;
            oss << buf[0];
            for (int i = 1; i < buf.size(); ++i)
            {
                oss << ' ' << buf[i];
            }
            res.push_back(oss.str());
        }
        for (int tail = head; tail < s.size(); ++tail)
        {
            string tmp = s.substr(head, tail - head + 1);
            if (words.find(tmp) != words.end())
            {
                buf.push_back(tmp);
                doWordBreak(s, tail+1, buf);
                buf.pop_back();
            }
        }
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for (int i = 0; i < wordDict.size(); ++i)
        {
            words.insert(wordDict[i]);
        }
        vector<string> buf;
        doWordBreak(s, 0, buf);
        return res;
    }
};