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.
Constraints:
- 1 <= s.length <= 20
- 1 <= wordDict.length <= 5000
- 1 <= wordDict[i].length <= 20
- s and wordDict[i] consist of only lowercase English letters.
Examples:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cat sand dog","cats and dog"]
Explanation: The output is a list of all possible sentences that can be formed using the given dictionary words.
Solutions
Backtracking with Memoization
The solution uses a backtracking approach with memoization to store the results of subproblems. It iterates over the string and checks if the current word is in the dictionary. If it is, it recursively calls the backtrack function with the next start position and adds the current word to the result.
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_map<int, vector<string>> memo;
function<vector<string>(int)> backtrack = [&](int start) {
if (start == s.size()) return {
""}
;
if (memo.count(start)) return memo[start];
vector<string> res;
for (int end = start + 1;
end <= s.size();
end++) {
string word = s.substr(start, end - start);
if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
vector<string> next = backtrack(end);
for (string sentence : next) {
res.push_back(word + (sentence.empty() ? "" : " " + sentence));
}
}
}
memo[start] = res;
return res;
}
;
return backtrack(0);
}Follow-up:
Word Break III: 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 the sentence with the maximum number of words.
