🗓️ Day 36: Word Break II — Return All Segmentations

🧠 Concept Deep Dive

Today we extend the Word Break problem to not just check if a word can be broken — but to return all possible segmentations.

Given s and wordDict, return all ways to break s into valid words.

We'll use recursion with memoization, and instead of returning booleans, we return arrays of sentences from each index.

🎯 Visual Intuition

Imagine this:

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

We want to find all sentences:

"cats and dog"
"cat sand dog"

Break from index 0:

"catsanddog"
├─ "cat" ✔ → recurse on "sanddog"
│                 ├─ "sand" ✔ → recurse on "dog"
│                 │             └─ "dog" ✔ ✅
├─ "cats" ✔ → recurse on "anddog"
│                  └─ "and" ✔ → "dog" ✔ ✅

Each path forms a full sentence.

🛠️ Key Patterns

💡 DFS + Memoization Returning Arrays

function wordBreak(s: string, wordDict: string[]): string[] {
  const wordSet = new Set(wordDict);
  const memo: Record<number, string[]> = {};

  const dfs = (start: number): string[] => {
    if (start === s.length) return [""];
    if (start in memo) return memo[start];

    const result: string[] = [];
    for (let end = start + 1; end <= s.length; end++) {
      const word = s.slice(start, end);
      if (wordSet.has(word)) {
        for (const sub of dfs(end)) {
          result.push(word + (sub ? " " + sub : ""));
        }
      }
    }
    return (memo[start] = result);
  };

  return dfs(0);
}

📘 Example

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"
]

🧪 Homework

Modify the function to return the number of possible segmentations.
Try a version without memoization and compare performance.
What if wordDict contains empty string? Should you handle that case?

🧠 Big-O Cheat Sheet

Time: O(2^n) worst case (exponential paths), but much faster with memoization
Space: O(n * k) — where k is the average number of splits from an index

🔮 Up Next

▶️ Day 37: Decode Ways — DP on Strings with Numbers