🗓️ Day 35: Word Break with Memoized Recursion

🧠 Concept Deep Dive

Today we tackle the classic Word Break problem using top-down recursion + memoization.

Given a string s and a dictionary wordDict, return whether s can be segmented into a space-separated sequence of one or more dictionary words.

This is a Dynamic Programming problem where we explore all prefixes and recursively check the rest of the string. To avoid recalculating subproblems, we use memoization.

🎯 Visual Intuition

Let's say:

s = "leetcode"
wordDict = ["leet", "code"]

We check prefixes like:

"l", "le", "lee", "leet" ✅ (in dictionary)
- Then recursively check "code" ✅

Use a Map<number, boolean> or array to memoize each starting index.

"leetcode"
  ├─ "leet" ✔ → check "code"
  │             └─ "code" ✔ → ✅
  └─ other prefixes ✘

🛠️ Key Patterns

💡 Memoized Recursion

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

  const canBreak = (start: number): boolean => {
    if (start === s.length) return true;
    if (start in memo) return memo[start];

    for (let end = start + 1; end <= s.length; end++) {
      const word = s.slice(start, end);
      if (wordSet.has(word) && canBreak(end)) {
        return (memo[start] = true);
      }
    }
    return (memo[start] = false);
  };

  return canBreak(0);
}

📘 Example

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

🧪 Homework

Modify the code to return all possible segmentations, not just true/false.
Try implementing the bottom-up DP version with a boolean array.
What happens if wordDict contains overlapping prefixes?

🧠 Big-O Cheat Sheet

Time: O(n^2) with memoization — due to nested loops
Space: O(n) for recursion + memo

🔮 Up Next

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