Given a string s and a dictionary of strings wordDict, return all possible sentences where s is segmented into dictionary words.
Input: s="catsanddog", wordDict=["cat","cats","and","sand","dog"] → Output: ["cats and dog","cat sand dog"]Input: s="pineapplepenapple", wordDict=["apple","pen","applepen","pine","pineapple"] → Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
DFS with memoization. At each starting position, try all dictionary words as next segment. Cache results per position.
- Build a Set from wordDict for O(1) lookup.
- DFS(start): try all substrings s[start..end] that exist in dict.
- Recursively get sentences for s[end..] and prepend current word.
- Memoize results by start index.
import java.util.*;
class Solution {
Map<Integer,List<String>> memo = new HashMap<>();
Set<String> dict;
public List<String> wordBreak(String s, List<String> wordDict) {
dict = new HashSet<>(wordDict);
return dfs(s, 0);
}
private List<String> dfs(String s, int start) {
if (memo.containsKey(start)) return memo.get(start);
List<String> res = new ArrayList<>();
if (start == s.length()) { res.add(""); return res; }
for (int end = start+1; end <= s.length(); end++) {
String word = s.substring(start, end);
if (dict.contains(word)) {
List<String> rest = dfs(s, end);
for (String r : rest) res.add(word + (r.isEmpty() ? "" : " " + r));
}
}
memo.put(start, res);
return res;
}
}
- Time Complexity: O(N^3 + 2^N) in worst case
- Space Complexity: O(N^2)