🗓️ Day 29: Word Break with DP + Trie

🧠 Concept Deep Dive

Word Break problems are all about checking if a given string can be broken into space-separated words from a dictionary.

There are two major approaches:

Dynamic Programming (DP): Track whether substrings can be broken using a dp[i] boolean array.
Trie + DFS + Memoization: Use a Trie to efficiently match prefixes and memoize subproblem results.

🎯 Visual Intuition

Let’s say we have s = "leetcode" and wordDict = ["leet", "code"]

String:  l  e  e  t  c  o  d  e
Index :  0  1  2  3  4  5  6  7
DP[i]: [T, F, F, F, T, F, F, F, T]

If dp[i] = true, it means substring s[0:i] can be segmented.

🛠️ Key Patterns

🧮 DP Table Based

function wordBreak(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict);
  const dp: boolean[] = Array(s.length + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[s.length];
}

🌲 Trie + Memoization (Advanced)

class TrieNode {
  children: { [key: string]: TrieNode } = {};
  isEnd = false;
}

class Trie {
  root = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const c of word) {
      if (!node.children[c]) node.children[c] = new TrieNode();
      node = node.children[c];
    }
    node.isEnd = true;
  }
}

function wordBreak(s: string, wordDict: string[]): boolean {
  const trie = new Trie();
  for (const word of wordDict) trie.insert(word);

  const memo: { [key: number]: boolean } = {};

  function dfs(start: number): boolean {
    if (start === s.length) return true;
    if (memo[start] !== undefined) return memo[start];

    let node = trie.root;
    for (let end = start; end < s.length; end++) {
      const char = s[end];
      if (!node.children[char]) break;
      node = node.children[char];
      if (node.isEnd && dfs(end + 1)) {
        memo[start] = true;
        return true;
      }
    }

    memo[start] = false;
    return false;
  }

  return dfs(0);
}

📘 Example

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

Output: true

Explanation: Can segment as "leet code"

🧪 Homework

Implement wordBreak() using DP.
Bonus: Implement using Trie + Memoization.

function wordBreak(s: string, wordDict: string[]): boolean {
  // your code
}

🧠 Big-O Cheat Sheet

DP Approach:
- Time: O(n^2) where n is the string length
- Space: O(n)
Trie + DFS + Memoization:
- Time: O(n * m) where m is max word length
- Space: O(n + k) where k is total Trie size

🔮 Up Next

▶️ Day 30: Palindrome Partitioning with Backtracking