128. Word Break II

For each starting index, try every dictionary word that matches the prefix from there, then recursively segment the rest. Cache the list of segmentations for each index so overlapping suffixes aren't recomputed.

Segment the suffix starting at each index

Define dfs(i) = all ways to break s[i:] into dictionary words, each returned as a list of words. Try every split point j such that s[i:j] is a dictionary word, then prepend it to every segmentation of s[j:].

def dfs(i):
    if i == len(s): return [[]]           # one empty segmentation
    if i in memo: return memo[i]
    out = []
    for j in i+1..len(s):
        w = s[i:j]
        if w in dict:
            for rest in dfs(j):
                out.append([w] + rest)
    memo[i] = out
    return out
return [" ".join(words) for words in dfs(0)]

Memoizing dfs(i) turns the exponential re-exploration into work proportional to the number of distinct suffixes, avoiding the classic TLE.

Worked example

s = "catsanddog", dict {cat, cats, and, sand, dog}.

• From index 0, "cat" matches → segment "sanddog" → "sand dog". Gives "cat sand dog".
• Also "cats" matches → segment "anddog" → "and dog". Gives "cats and dog".

Result: ["cat sand dog", "cats and dog"].

Complexity

• Time: O(n^2 · 2^n) worst case (number of segmentations can be exponential), but memoization shares suffix work.
• Space: O(n · number of results).

class Solution {
    public String[] wordBreak(String s, String[] wordDict) {
        Set<String> words = new HashSet<>(Arrays.asList(wordDict));
        Map<Integer, List<String>> memo = new HashMap<>();
        List<String> out = dfs(s, 0, words, memo);
        return out.toArray(new String[0]);
    }

    // returns all segmentations of s[i:] as space-joined sentences.
    private List<String> dfs(String s, int i, Set<String> words, Map<Integer, List<String>> memo) {
        if (memo.containsKey(i)) return memo.get(i);
        List<String> res = new ArrayList<>();
        if (i == s.length()) {
            res.add("");
            memo.put(i, res);
            return res;
        }
        for (int j = i + 1; j <= s.length(); j++) {
            String w = s.substring(i, j);
            if (words.contains(w)) {
                for (String rest : dfs(s, j, words, memo)) {
                    res.add(rest.isEmpty() ? w : w + " " + rest);
                }
            }
        }
        memo.put(i, res);
        return res;
    }
}