Problem
Given a string s and a dictionary, return all possible sentences where words from the dictionary form s.
Example
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]Solution
DP with memoization. For each position, try all dictionary words starting there.
def word_break(s, word_dict):
word_set = set(word_dict)
memo = {}
def dfs(i):
if i in memo: return memo[i]
if i == len(s): return ['']
result = []
for j in range(i + 1, len(s) + 1):
word = s[i:j]
if word in word_set:
for rest in dfs(j):
result.append(word + (' ' + rest if rest else ''))
memo[i] = result
return result
return dfs(0)function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const memo = new Map();
function dfs(i) {
if (memo.has(i)) return memo.get(i);
if (i === s.length) return [''];
const result = [];
for (let j = i + 1; j <= s.length; j++) {
const word = s.substring(i, j);
if (wordSet.has(word)) {
for (const rest of dfs(j)) {
result.push(word + (rest ? ' ' + rest : ''));
}
}
}
memo.set(i, result);
return result;
}
return dfs(0);
}class Solution {
unordered_set<string> dict;
unordered_map<int, vector<string>> memo;
vector<string> dfs(string& s, int i) {
if (memo.count(i)) return memo[i];
if (i == s.size()) return {""};
vector<string> result;
for (int j = i + 1; j <= s.size(); j++) {
string word = s.substr(i, j - i);
if (dict.count(word)) {
for (string& rest : dfs(s, j)) {
result.push_back(word + (rest.empty() ? "" : " " + rest));
}
}
}
memo[i] = result;
return result;
}
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
dict = unordered_set<string>(wordDict.begin(), wordDict.end());
return dfs(s, 0);
}
};public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
Map<Integer, List<String>> memo = new HashMap<>();
return dfs(s, 0, set, memo);
}
private List<String> dfs(String s, int i, Set<String> set, Map<Integer, List<String>> memo) {
if (memo.containsKey(i)) return memo.get(i);
if (i == s.length()) return Arrays.asList("");
List<String> result = new ArrayList<>();
for (int j = i + 1; j <= s.length(); j++) {
String word = s.substring(i, j);
if (set.contains(word)) {
for (String rest : dfs(s, j, set, memo)) {
result.add(word + (rest.isEmpty() ? "" : " " + rest));
}
}
}
memo.put(i, result);
return result;
}Complexity
- Time: O(n³)
- Space: O(n²)
Explanation
Memoization avoids recomputing sentences from the same starting position. Without it, the recursion tree explodes exponentially.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?