211. Word Break

🔗 LeetCode Problem: 139. Word Break
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, String, Hash Table, Trie, Memoization, 1D DP

Problem Statement

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

Note: The same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

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

Constraints: - 1 <= s.length <= 300 - 1 <= wordDict.length <= 1000 - 1 <= wordDict[i].length <= 20 - s and wordDict[i] consist of only lowercase English letters. - All the strings of wordDict are unique.

---

🌳 Visual Understanding - Using "applepenapple"

The Problem We're Solving:

Given: String s = "applepenapple"
       Dictionary = ["apple", "pen"]

Goal: Can we build s using ONLY dictionary words?

Question: Can "applepenapple" be made from "apple" and "pen"? 🤔

Finding the Solution for "applepenapple":

String: "applepenapple"
Dictionary: ["apple", "pen"]

Let's try to segment it:

Position 0-4: "apple" 
  ✓ "apple" is in dictionary!
  Remaining: "penapple"

Position 5-7: "pen"
  ✓ "pen" is in dictionary!
  Remaining: "apple"

Position 8-12: "apple"
  ✓ "apple" is in dictionary! (reusing word!)
  Remaining: "" (empty - we're done!)

Segmentation: "apple" + "pen" + "apple" ✓
Answer: true

Notice: We used "apple" TWICE (word reuse allowed!)

Why This Example Is Great:

"applepenapple" teaches us:

1. WORD REUSE: 
   - "apple" appears twice
   - Dictionary words can repeat!

2. GREEDY DOESN'T WORK:
   - Can't just take longest match first
   - Need to try different combinations

3. MULTIPLE DECISIONS:
   - At each position, multiple choices possible
   - Need to explore carefully!

This is why we need DP! 🎯

Complete Decision Tree for "applepenapple":

                    "applepenapple"
                          |
    +---------------------+---------------------+
    |                     |                     |
  "a"                  "apple"              "applepe"
(not in dict)         (in dict ✓)          (not in dict)
  DEAD                    |                   DEAD
                          v
                    "penapple"
                          |
    +---------------------+---------------------+
    |                     |                     |
  "p"                   "pen"                "penap"
(not in dict)         (in dict ✓)          (not in dict)
  DEAD                    |                   DEAD
                          v
                      "apple"
                          |
                    +-----+-----+
                    |           |
                 "apple"      "applepe"
                (in dict ✓)  (not in dict)
                    |           DEAD
                    v
                   "" (empty)
                  SUCCESS! ✓

Result: true - Found valid segmentation!
Segmentation: "apple" → "pen" → "apple"

Failed Example: "catsandog"

String: "catsandog"
Dictionary: ["cats", "dog", "sand", "and", "cat"]

Let's see why this FAILS:

Try 1: "cat" + "sandog"
  ✓ "cat" is in dictionary
  ✗ "sandog" is NOT in dictionary
  FAILED!

Try 2: "cats" + "andog"
  ✓ "cats" is in dictionary
  ✗ "andog" is NOT in dictionary
  FAILED!

Try 3: "cat" + "sand" + "og"
  ✓ "cat" is in dictionary
  ✓ "sand" is in dictionary
  ✗ "og" is NOT in dictionary
  FAILED!

Try 4: "cats" + "and" + "og"
  ✓ "cats" is in dictionary
  ✓ "and" is in dictionary
  ✗ "og" is NOT in dictionary
  FAILED!

No matter how we segment, we get stuck with "og"!
Answer: false

---

🧠 The AHA Moment - Why This Problem Needs DP

What Makes This Hard?

CHALLENGE 1: Multiple ways to start
  "applepenapple" could start with:
    - "a" (not in dict)
    - "ap" (not in dict)
    - "app" (not in dict)
    - "appl" (not in dict)
    - "apple" (in dict!) ✓
    - "applep" (not in dict)
    ...

  We must try many possibilities!

CHALLENGE 2: Same subproblems appear multiple times
  If we try "cat" first: need to solve "sandog"
  If we try "cats" first: need to solve "andog"
  Both might later need to check "og"!

  Checking "og" multiple times is wasteful! ⚠️

CHALLENGE 3: Greedy doesn't work
  Can't just take the longest matching word first

  Example: "aaaaaaaaaaaab" with dict = ["a", "aa", "aaaa", "aaaaa"]
  Greedy (longest): Take "aaaaa" → "aaaab" → stuck!
  Optimal: Take "a" many times → "b" → check if possible

  Need to try different combinations! 🎯

This is a PERFECT DP problem!

The Key Insight - Think Backwards!

CLEVER THINKING:

Instead of: "Can I segment the whole string?"
Think: "Can I segment from each position to the end?"

For "applepenapple":

  Position 13 (end): Empty string → YES (base case)

  Position 12: "e" 
    → Can we make "e" and reach end? NO

  Position 8: "apple"
    → Can we make "apple" and reach end?
    → "apple" in dict? YES
    → Can we segment from position 13? YES
    → So position 8 works! ✓

  Position 5: "penapple"
    → Can we make "pen" and reach position 8?
    → "pen" in dict? YES
    → Can we segment from position 8? YES (we know this!)
    → So position 5 works! ✓

  Position 0: "applepenapple"
    → Can we make "apple" and reach position 5?
    → "apple" in dict? YES
    → Can we segment from position 5? YES (we know this!)
    → So position 0 works! ✓

If position 0 works, entire string can be segmented! 🎯

Why DP? Two Key Properties:

1. OVERLAPPING SUBPROBLEMS:

   To check "applepenapple":
     - If we take "apple": need to check "penapple"
     - If we take "app" (if it existed): might also need "penapple"

   Same suffixes checked multiple times!
   Solution: Remember results! (Memoization)

2. OPTIMAL SUBSTRUCTURE:

   canSegment("applepenapple") depends on:
     - Can we match a word at start?
     - Can we segment what remains?

   Solution to big problem uses solutions to smaller problems!

These properties = Classic DP! 🎯

---

🔴 Approach 1: Brute Force Recursion (Try Every Possibility)

📐 Function Definition

Function Signature:

boolean wordBreak(String s, List<String> wordDict)
boolean canSegment(String s, Set<String> wordSet, int start)

What it represents:

Input Parameter s: - The string we're trying to segment - Example: s = "applepenapple"

Input Parameter start: - Current position in string - We're checking if s[start..end] can be segmented - Example: start=5 means "can we segment 'penapple'?"

Input Parameter wordSet: - Dictionary converted to HashSet for O(1) lookup - Example: {"apple", "pen"}

Return Value (boolean): - true = Can segment s[start..end] using dictionary - false = Cannot segment s[start..end]

Purpose: - Try every possible first word from current position - Recursively check if remaining can be segmented - Return true if ANY combination works

Key Understanding:

canSegment("applepenapple", wordSet, 0) means:
  "Can we segment 'applepenapple' from position 0?"

At position 0, we try all possible first words:
  - "a" (position 0-0): not in dict, skip
  - "ap" (position 0-1): not in dict, skip
  - "app" (position 0-2): not in dict, skip
  - "appl" (position 0-3): not in dict, skip
  - "apple" (position 0-4): in dict! ✓
    → Check if we can segment from position 5
    → If YES, we found a solution!

Keep trying until we find a valid segmentation!

💡 Intuition

The simplest idea: Try every possible way to cut the string!

Think of it like cutting a chocolate bar:

"applepenapple" - where should I make the first cut?

Option 1: Cut after "a"
  → Got "a"
  → "a" in dictionary? NO
  → Skip this option

Option 2: Cut after "ap"  
  → Got "ap"
  → "ap" in dictionary? NO
  → Skip this option

Option 3: Cut after "app"
  → Got "app"
  → "app" in dictionary? NO
  → Skip this option

Option 4: Cut after "appl"
  → Got "appl"
  → "appl" in dictionary? NO
  → Skip this option

Option 5: Cut after "apple"
  → Got "apple"
  → "apple" in dictionary? YES! ✓
  → Now recursively check remaining "penapple"
  → If remaining works, we're done!

For each valid first word, recursively solve what's left!
This explores ALL possible segmentations!

The Recursive Pattern:

At each position:
  1. TRY: all possible word lengths from this position
  2. CHECK: is this substring in dictionary?
  3. RECURSE: if YES, check if remaining can be segmented
  4. RETURN: true if ANY option works
  5. BASE CASE: if we reach the end, return true

This naturally tries every possible combination!

📝 Implementation

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // Convert to HashSet for O(1) lookup (CRITICAL!)
        Set<String> wordSet = new HashSet<>(wordDict);
        return canSegment(s, wordSet, 0);
    }

    private boolean canSegment(String s, Set<String> wordSet, int start) {
        // Base case: reached end of string
        if (start == s.length()) {
            return true;  // Successfully segmented entire string!
        }

        // Try all possible word lengths from current position
        for (int end = start + 1; end <= s.length(); end++) {
            // Extract substring from start to end
            String word = s.substring(start, end);

            // If this word is in dictionary
            if (wordSet.contains(word)) {
                // Recursively check if remaining can be segmented
                if (canSegment(s, wordSet, end)) {
                    return true;  // Found valid segmentation!
                }
            }
        }

        // No valid segmentation found from this position
        return false;
    }
}

🔍 Detailed Dry Run: s = "applepenapple", wordDict = ["apple", "pen"]

wordSet = {"apple", "pen"}

canSegment("applepenapple", wordSet, 0)
├─ start=0, length=13
├─ Try all word lengths from position 0
│
├─ Try s[0..1] = "a": not in dict, skip
├─ Try s[0..2] = "ap": not in dict, skip
├─ Try s[0..3] = "app": not in dict, skip
├─ Try s[0..4] = "appl": not in dict, skip
├─ Try s[0..5] = "apple": in dict! ✓
│  └─ canSegment("applepenapple", wordSet, 5)
│     ├─ start=5, remaining="penapple"
│     ├─ Try all word lengths from position 5
│     │
│     ├─ Try s[5..6] = "p": not in dict, skip
│     ├─ Try s[5..7] = "pe": not in dict, skip
│     ├─ Try s[5..8] = "pen": in dict! ✓
│     │  └─ canSegment("applepenapple", wordSet, 8)
│     │     ├─ start=8, remaining="apple"
│     │     ├─ Try all word lengths from position 8
│     │     │
│     │     ├─ Try s[8..9] = "a": not in dict, skip
│     │     ├─ Try s[8..10] = "ap": not in dict, skip
│     │     ├─ Try s[8..11] = "app": not in dict, skip
│     │     ├─ Try s[8..12] = "appl": not in dict, skip
│     │     ├─ Try s[8..13] = "apple": in dict! ✓
│     │     │  └─ canSegment("applepenapple", wordSet, 13)
│     │     │     └─ start=13 == length → BASE CASE
│     │     │        return true ✓
│     │     │
│     │     └─ return true (found "apple")
│     │
│     └─ return true (found "pen")
│
└─ return true (found "apple")

Result: true ✓

Segmentation found: "apple" → "pen" → "apple"

What Happens Step-by-Step:

Position 0: "applepenapple"
  ✓ Found "apple" (0-5)
  → Recurse to position 5

Position 5: "penapple"
  ✓ Found "pen" (5-8)
  → Recurse to position 8

Position 8: "apple"
  ✓ Found "apple" (8-13)
  → Recurse to position 13

Position 13: "" (empty)
  ✓ Reached end! Success!

Backtrack with "true" all the way up!

The Problem - Exponential Time:

For "aaaaaaaaaa" with dict = ["a", "aa", "aaa", ...]:

  At position 0:
    Try "a" → recurse to position 1
    Try "aa" → recurse to position 2
    Try "aaa" → recurse to position 3
    ...

  This creates exponential branches!
  Many positions checked multiple times!

  For n=10: Could check same suffixes hundreds of times!

  This is TOO SLOW! ⚠️

📊 Complexity Analysis

Time Complexity: O(2^n)

At each position, multiple choices
Each choice creates a branch
Creates exponential recursion tree

For long strings: TOO SLOW! ❌

Space Complexity: O(n)

Recursion stack depth: O(n) worst case

Why This Fails:

❌ Exponential time - too slow
❌ Rechecks same positions many times
❌ No memory of previous results
✅ But shows the recursive structure clearly!

---

🟡 Approach 2: Top-Down DP (Remember What We've Seen)

📐 Function Definition

Function Signature:

boolean canSegment(String s, Set<String> wordSet, int start, Boolean[] memo)

What it represents:

Input Parameter memo (Boolean[]): - Memory array to store results - memo[i] = can we segment s[i..end]? - null = haven't checked yet - true = yes, can segment - false = no, cannot segment

Purpose: - Same recursion as Approach 1 - BUT remember results to avoid rechecking - Each position calculated at most once!

Key Understanding:

First time at position 5:
  - memo[5] = null (not checked)
  - Calculate: Can we segment "penapple"?
  - Result: true
  - Store: memo[5] = true
  - Return: true

Second time at position 5 (if we get here again):
  - memo[5] = true (already know!)
  - Return immediately: true
  - No recalculation! ✨

This saves TONS of time!

💡 Intuition

Super simple idea: Remember what we've already figured out!

Imagine you're solving a maze:

WITHOUT MEMORY (Approach 1):
  Every time you reach a junction you've seen before,
  you explore it again from scratch.
  Waste of time! ⚠️

WITH MEMORY (Approach 2):
  First time at a junction: Explore it, remember result
  Next time at same junction: "Oh, I've been here!"
    → Use remembered result
    → No need to explore again! ✨

For "applepenapple":
  First time we check position 8:
    → Calculate: "apple" can be segmented? YES
    → Remember: memo[8] = true

  If we ever need position 8 again:
    → Look up: memo[8] = true
    → Return immediately!

This is called MEMOIZATION - just fancy word for "remembering"!

📝 Implementation

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        // Create memory array (one extra for position n)
        Boolean[] memo = new Boolean[s.length() + 1];
        return canSegment(s, wordSet, 0, memo);
    }

    private boolean canSegment(String s, Set<String> wordSet, 
                               int start, Boolean[] memo) {
        // Base case
        if (start == s.length()) {
            return true;
        }

        // Check if we've already solved this position
        if (memo[start] != null) {
            return memo[start];  // Return remembered result! ✨
        }

        // Try all possible word lengths
        for (int end = start + 1; end <= s.length(); end++) {
            String word = s.substring(start, end);

            if (wordSet.contains(word)) {
                if (canSegment(s, wordSet, end, memo)) {
                    memo[start] = true;  // Remember: YES!
                    return true;
                }
            }
        }

        // No valid segmentation found
        memo[start] = false;  // Remember: NO!
        return false;
    }
}

🔍 Detailed Dry Run: s = "applepenapple"

memo = [null, null, null, null, null, null, null, null, null, null, null, null, null, null]
        ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑     ↑
        0     1     2     3     4     5     6     7     8     9     10    11    12    13

canSegment(s, wordSet, 0, memo)
├─ memo[0] = null → not calculated yet
├─ Try "apple" (0-5): in dict ✓
│  └─ canSegment(s, wordSet, 5, memo)
│     ├─ memo[5] = null → not calculated yet
│     ├─ Try "pen" (5-8): in dict ✓
│     │  └─ canSegment(s, wordSet, 8, memo)
│     │     ├─ memo[8] = null → not calculated yet
│     │     ├─ Try "apple" (8-13): in dict ✓
│     │     │  └─ canSegment(s, wordSet, 13, memo)
│     │     │     └─ start == length → return true
│     │     │
│     │     ├─ Found solution!
│     │     ├─ memo[8] = true ✓ (remember!)
│     │     └─ return true
│     │
│     ├─ Found solution!
│     ├─ memo[5] = true ✓ (remember!)
│     └─ return true
│
├─ Found solution!
├─ memo[0] = true ✓ (remember!)
└─ return true

Final memo state:
memo = [true, null, null, null, null, true, null, null, true, null, null, null, null, null]
        ↑                                 ↑                   ↑
     Position 0                       Position 5          Position 8
   "applepenapple"                    "penapple"           "apple"
      can segment!                    can segment!       can segment!

Result: true ✓

Why This Is Much Faster:

Each position checked at most ONCE!

Position 0: Check once, remember result
Position 5: Check once, remember result
Position 8: Check once, remember result
Position 13: Base case (always true)

If we had multiple paths to position 8:
  First path: Calculate and store memo[8] = true
  Other paths: Just read memo[8] = true immediately!

Instead of exponential, now it's polynomial! 🚀

📊 Complexity Analysis

Time Complexity: O(n² × m)

n positions to check: O(n)
Each position tries up to n substrings: O(n)
Each substring check in HashSet: O(m) where m = avg word length

Total: O(n × n × m) = O(n² × m)

MUCH better than O(2^n)! 🚀

Space Complexity: O(n)

Memo array: O(n)
Recursion stack: O(n)
Total: O(n)

---

🟢 Approach 3: Bottom-Up DP (Build Solution from End to Start)

📐 Function Definition

DP Array Definition:

boolean[] dp = new boolean[n + 1];

What dp[i] represents:

Index i: - Position in the string - dp[i] represents s[i..end]

Value dp[i] (boolean): - dp[i] = true → Can segment s[i..end] using dictionary - dp[i] = false → Cannot segment s[i..end]

Purpose: - Build solution table from END to START - No recursion needed! - Fill table once, use directly

Key Understanding:

For "applepenapple" (length 13):

dp[13] = true (empty string - base case)
dp[12] = ? (can segment "e"?)
dp[11] = ? (can segment "le"?)
...
dp[8] = ? (can segment "apple"?)
...
dp[5] = ? (can segment "penapple"?)
...
dp[0] = ? (can segment entire string?)

Build from right to left!
dp[0] = final answer!

💡 Intuition

Think of it like climbing stairs backwards:

Instead of top-down recursion (going down),
we build bottom-up (climbing up from end)!

For "applepenapple":

Start at END (position 13):
  dp[13] = true (empty string always works)

Work BACKWARDS to position 12:
  Can we segment "e"?
  Try all dictionary words:
    - "apple" too long
    - "pen" too long
  Result: dp[12] = false

Work BACKWARDS to position 11:
  Can we segment "le"?
  Try all dictionary words:
    - "apple" too long
    - "pen" too long
  Result: dp[11] = false

Continue...

Work BACKWARDS to position 8:
  Can we segment "apple"?
  Try "apple": matches! ✓
    Check dp[13] = true ✓
  Result: dp[8] = true ✓

Continue...

Work BACKWARDS to position 5:
  Can we segment "penapple"?
  Try "pen": matches! ✓
    Check dp[8] = true ✓ (we already know this!)
  Result: dp[5] = true ✓

Continue...

Work BACKWARDS to position 0:
  Can we segment "applepenapple"?
  Try "apple": matches! ✓
    Check dp[5] = true ✓ (we already know this!)
  Result: dp[0] = true ✓

Answer is dp[0]! 🎯

Why Build Backwards?

KEY INSIGHT:

To know if position i works:
  Need to know if positions i+1, i+2, ... work!

Example:
  To know dp[5] ("penapple"):
    If "pen" matches, need dp[8]
    dp[8] must be calculated FIRST!

Building backwards ensures all dependencies ready!

Direction: 13 → 12 → 11 → ... → 1 → 0

📝 Implementation

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> wordSet = new HashSet<>(wordDict);

        // dp[i] = can we segment s[i..end]?
        boolean[] dp = new boolean[n + 1];

        // Base case: empty string (position n)
        dp[n] = true;

        // Build backwards from end to start
        for (int i = n - 1; i >= 0; i--) {
            // Try all words from dictionary
            for (String word : wordSet) {
                int len = word.length();

                // Check if word fits at position i
                if (i + len <= n && s.substring(i, i + len).equals(word)) {
                    // If word matches AND remaining can be segmented
                    if (dp[i + len]) {
                        dp[i] = true;
                        break;  // Found a valid word, no need to check more
                    }
                }
            }
        }

        // Answer: can we segment from start?
        return dp[0];
    }
}

🔍 Detailed Dry Run: s = "applepenapple"

s = "applepenapple"
n = 13
wordSet = {"apple", "pen"}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Create DP table:
dp = [false, false, false, false, false, false, false, false, false, false, false, false, false, false]
      ↑      ↑      ↑      ↑      ↑      ↑      ↑      ↑      ↑      ↑      ↑      ↑      ↑      ↑
      0      1      2      3      4      5      6      7      8      9      10     11     12     13

Base case:
dp[13] = true (empty string)

dp = [false, false, false, false, false, false, false, false, false, false, false, false, false, true]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILDING BACKWARDS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Position 12: s[12..13] = "e"
━━━━━━━━━━━━━━━━━━━━━━━━
Try "apple": len=5, 12+5=17 > 13, too long
Try "pen": len=3, 12+3=15 > 13, too long
No match → dp[12] = false

Position 11: s[11..13] = "le"
━━━━━━━━━━━━━━━━━━━━━━━━━
Try "apple": len=5, 11+5=16 > 13, too long
Try "pen": len=3, 11+3=14 > 13, too long
No match → dp[11] = false

Position 10: s[10..13] = "ple"
━━━━━━━━━━━━━━━━━━━━━━━━━━
Try "apple": len=5, 10+5=15 > 13, too long
Try "pen": len=3, 10+3=13 ✓
  s[10..13] = "ple"
  "ple" == "pen"? NO
Try more...
No match → dp[10] = false

...continuing backwards...

Position 8: s[8..13] = "apple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Try "apple": len=5, 8+5=13 ✓
  s[8..13] = "apple"
  "apple" == "apple"? YES! ✓
  Check dp[13] = true ✓

  dp[8] = true ✓
  Break (found match)

dp = [false, false, false, false, false, false, false, false, true, false, false, false, false, true]
                                                                    ↑
                                                              "apple" works!

Position 7: s[7..13] = "papple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
No match → dp[7] = false

Position 6: s[6..13] = "napple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
No match → dp[6] = false

Position 5: s[5..13] = "penapple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Try "apple": len=5, 5+5=10 ✓
  s[5..10] = "penap"
  "penap" == "apple"? NO

Try "pen": len=3, 5+3=8 ✓
  s[5..8] = "pen"
  "pen" == "pen"? YES! ✓
  Check dp[8] = true ✓

  dp[5] = true ✓
  Break (found match)

dp = [false, false, false, false, false, true, false, false, true, false, false, false, false, true]
                                                ↑
                                           "pen" works!

Position 4: s[4..13] = "epenapple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
No match → dp[4] = false

Position 3: s[3..13] = "lepenapple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
No match → dp[3] = false

Position 2: s[2..13] = "plepenapple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
No match → dp[2] = false

Position 1: s[1..13] = "pplepenapple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
No match → dp[1] = false

Position 0: s[0..13] = "applepenapple"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Try "apple": len=5, 0+5=5 ✓
  s[0..5] = "apple"
  "apple" == "apple"? YES! ✓
  Check dp[5] = true ✓

  dp[0] = true ✓
  Break (found match)

Final DP table:
dp = [true, false, false, false, false, true, false, false, true, false, false, false, false, true]
      ↑                                 ↑                   ↑                                      ↑
   Position 0                       Position 5          Position 8                            Position 13
"applepenapple"                    "penapple"           "apple"                               (empty)
  CAN segment!                     CAN segment!       CAN segment!                          base case

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: dp[0] = true ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Segmentation path:
  dp[0] → "apple" → dp[5]
  dp[5] → "pen" → dp[8]
  dp[8] → "apple" → dp[13]
  dp[13] → empty (success!)

Segmentation: "apple" + "pen" + "apple" ✓

Why This Is Beautiful:

ADVANTAGES:
✅ No recursion - just simple loop
✅ Clear building process
✅ All positions calculated exactly once
✅ Easy to debug (can print table)
✅ Optimal time complexity

The dp table shows exactly which positions work!
dp[i] = true means "can segment from i to end"

📊 Complexity Analysis

Time Complexity: O(n × k × m)

n positions: O(n)
For each position, try k dictionary words: O(k)
Each word comparison: O(m) where m = avg word length

Total: O(n × k × m)

Typically: O(n² × m) considering all substrings

Space Complexity: O(n)

DP table: O(n)
No recursion: O(1)
Total: O(n)

---

🔵 Approach 4: Bottom-Up DP (Forward Direction - Alternative)

📐 Function Definition

DP Array Definition:

boolean[] dp = new boolean[n + 1];

What dp[i] represents (DIFFERENT!):

Index i: - Number of characters processed - dp[i] represents s[0..i-1] (first i characters)

Value dp[i] (boolean): - dp[i] = true → Can segment s[0..i-1] (first i characters) - dp[i] = false → Cannot segment first i characters

Purpose: - Build solution from START to END (opposite direction!) - Still no recursion - Just different perspective

Key Understanding:

For "applepenapple" (length 13):

dp[0] = true (0 characters = empty string, base case)
dp[1] = ? (can segment "a"?)
dp[2] = ? (can segment "ap"?)
...
dp[5] = ? (can segment "apple"?)
...
dp[8] = ? (can segment "applepen"?)
...
dp[13] = ? (can segment entire string?)

Build from left to right!
dp[13] = final answer!

💡 Intuition

Think of it as building the string piece by piece:

Start with EMPTY string (position 0):
  dp[0] = true (can segment empty string)

Add characters one by one:

Position 1: "a"
  Can we make "a"?
  Check if previous (dp[0]=true) AND "a" in dict
  "a" not in dict → dp[1] = false

Position 2: "ap"
  Can we make "ap"?
  Could be: dp[0] + "ap" (not in dict)
  Could be: dp[1] + "p" (dp[1]=false, skip)
  Result: dp[2] = false

...

Position 5: "apple"
  Can we make "apple"?
  Could be: dp[0] + "apple" (in dict!) ✓
    dp[0] = true ✓
    "apple" in dict ✓
  Result: dp[5] = true ✓

Position 8: "applepen"
  Can we make "applepen"?
  Could be: dp[5] + "pen" (in dict!) ✓
    dp[5] = true ✓
    "pen" in dict ✓
  Result: dp[8] = true ✓

Position 13: "applepenapple"
  Can we make "applepenapple"?
  Could be: dp[8] + "apple" (in dict!) ✓
    dp[8] = true ✓
    "apple" in dict ✓
  Result: dp[13] = true ✓

Same answer, different direction! 🎯

📝 Implementation

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> wordSet = new HashSet<>(wordDict);

        // dp[i] = can we segment s[0..i-1] (first i characters)?
        boolean[] dp = new boolean[n + 1];

        // Base case: empty string (0 characters)
        dp[0] = true;

        // Build forward from start to end
        for (int i = 1; i <= n; i++) {
            // Try all possible previous positions
            for (int j = 0; j < i; j++) {
                // If first j characters can be segmented
                // AND s[j..i-1] is in dictionary
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;  // Found valid segmentation
                }
            }
        }

        return dp[n];
    }
}

📊 Complexity Analysis

Time Complexity: O(n² × m) Space Complexity: O(n)

Same as Approach 3, just different direction!

---

🎯 Pattern Recognition - String Segmentation

Core Pattern: Can We Build This String?

Template for segmentation problems:

Goal: Can we build string s using dictionary words?

DP Approach:
  dp[i] = can we segment up to position i?

  For each position i:
    Try all valid segments ending at i
    If segment valid AND previous position works:
      → dp[i] = true

Similar Problems:
- Palindrome Partitioning: Segment into palindromes
- Decode Ways: Segment with decoding rules
- Sentence Screen Fitting: Segment with word wrapping

When to Use This Pattern:

✅ Need to break string into pieces
✅ Each piece must satisfy some condition
✅ Need to check if entire string can be broken
✅ Order matters (left to right)
✅ Pieces can repeat

For Word Break:
✅ Break into dictionary words
✅ Words must be in dictionary
✅ Check if entire string breakable
✅ Order matters
✅ Words can repeat

---

⚠️ Important Edge Cases to Test

s = "a", wordDict = ["a"]                    // Expected: true
s = "a", wordDict = ["b"]                    // Expected: false
s = "applepenapple", wordDict = ["apple","pen"] // Expected: true (reuse)
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] // Expected: false
s = "aaaaaaa", wordDict = ["aaaa","aaa"]     // Expected: true
s = "aaaaaaa", wordDict = ["aaaa","aa"]      // Expected: false
s = "bb", wordDict = ["a","b","bbb","bbbb"]  // Expected: true
s = "", wordDict = ["a"]                     // Expected: true (empty string)
s = "cars", wordDict = ["car","ca","rs"]     // Expected: true
s = "abcd", wordDict = ["a","abc","b","cd"]  // Expected: true

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Given string and dictionary, check if string can be segmented using dictionary words (reuse allowed).

Key Insight: Try each position - can we match a word AND segment the rest? Use DP to remember results.

Four Approaches: 1. Brute Force → Try every segmentation, O(2^n) ❌ 2. Top-Down DP → Remember results, O(n² × m) ✓ 3. Bottom-Up Backward → Build from end, O(n² × m) ✓ 4. Bottom-Up Forward → Build from start, O(n² × m) ⭐

⚡ Quick Implementation

import java.util.HashSet;
import java.util.List;

public class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    HashSet<String> dict = new HashSet<>(wordDict);

    // // Approach 1 - brute force
    // // Step 1: Can we segment string s starting from index 0 to end?
    // return recursive(s, 0, dict);

    // // Approach 2 - top down
    // Boolean[] memo = new Boolean[s.length()];
    // return topDown(s, 0, dict, memo);

    // // Approach 3 - bottom up
    // return bottomUpBackward(s, dict);

    // Approach 4 - bottom up (forward)
    return bottomUpForward(s, dict);
  }

  private boolean bottomUpForward(String s, HashSet<String> dict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true; // an empty string can be always segmented

    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < i; j++) {
        // Try every substring from (j, i)
        String word = s.substring(j, i);

        // check if this substring exists in dict.
        // If yes, check if string before j is segmented.
        // "applepenapple" => dp[0]=T, dp[5]=T only if dp[0]=T
        // Means, for dp[5], "apple" is in dict.
        // Similarly, for dp[8], "pen" is in dict and dp[8]=T only
        // when dp[5] is T (already segmented)
        if (dict.contains(word) && dp[i - word.length()]) {
          dp[i] = true;
        }
      }
    }

    return dp[n];
  }

  private boolean bottomUpBackward(String s, HashSet<String> dict) {
    int n = s.length();
    // dp[i] => string from index i to end can be segmented or not?
    // For "applepenapple" (length 13):
    // dp[13] = true (empty string - base case)
    // dp[12] = ? (can segment "e"?)
    boolean[] dp = new boolean[n + 1];
    dp[n] = true; // an empty string can be always segmented

    for (int i = n - 1; i >= 0; i--) {
      // We need to check if s[i...end] is in dict.
      // dp[12] = "e". Check if this exists in dict.
      // Similarly, dp[8] = "apple" needs to be checked in dict.
      // If yes, we need to check if dp[13] is also segmented (remaining)

      // compare this s[i...end] with all the words in the dict.
      for (String word : dict) {
        int wordLen = word.length();

        if (i + wordLen <= n && s.substring(i, i + wordLen).equals(word) && dp[i + wordLen]) {
          dp[i] = true;

          break;
        }
      }
    }

    return dp[0];
  }

  private boolean topDown(String s, int start, HashSet<String> dict, Boolean[] memo) {
    if (start == s.length()) {
      return true;
    }

    if (memo[start] != null) {
      return memo[start];
    }

    for (int end = start; end < s.length(); end++) {
      if (dict.contains(s.substring(start, end + 1))) {
        if (topDown(s, end + 1, dict, memo)) {
          return memo[start] = true;
        }
      }
    }

    return memo[start] = false;
  }

  private boolean recursive(String s, int start, HashSet<String> dict) {
    // step 4: if reached the string end, we are done. Return true.
    if (start == s.length()) {
      return true;
    }

    // Step 2: can we segment from start to end (find this part in dict)?
    // If yes, start from next index if we can segment from there.
    for (int end = start; end < s.length(); end++) {
      if (dict.contains(s.substring(start, end + 1))) {
        // step 3: try from next index to segment
        if (recursive(s, end + 1, dict)) {
          return true;
        }
      }
    }

    return false;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.wordBreak("leetcode", List.of("leet", "code")) == true);
    System.out.println(s.wordBreak("applepenapple", List.of("apple", "pen")) == true);
    System.out.println(s.wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")) == false);

  }
}

🔑 Key Insights

CRITICAL: HashSet Conversion:

Set<String> wordSet = new HashSet<>(wordDict);

WHY THIS MATTERS:
  List.contains(): O(k) - checks every word
  Set.contains(): O(1) - instant lookup!

Without HashSet: O(n² × k × m)
With HashSet: O(n² × m)

This optimization is ESSENTIAL! 🚀

Word Reuse Allowed:

"applepenapple" with ["apple", "pen"]
→ Use "apple" TWICE! ✓

No tracking needed - just keep trying words!
This makes problem simpler than it looks!

Two Valid Directions:

BACKWARD: dp[i] = segment s[i..end]
  Base: dp[n] = true
  Answer: dp[0]

FORWARD: dp[i] = segment s[0..i-1]
  Base: dp[0] = true
  Answer: dp[n]

Both work! Forward is more intuitive.

🎪 Memory Aid

"HashSet first, then DP!"
"Words can repeat - no problem!"
"Forward or backward - your choice!"
"Try all splits, remember results!" ✨

⚠️ Common Mistakes

• ❌ Using List instead of HashSet (super slow!)
• ❌ Not allowing word reuse
• ❌ Off-by-one in substring indices
• ❌ Forgetting base case (dp[0] or dp[n])
• ❌ Not breaking after finding valid segmentation

✅ Interview Talking Points

"This is a string segmentation DP problem.

Intuition:
  At each position, ask: Can we match a dictionary word
  AND successfully segment what remains?

Approach (Forward DP):
  1. Convert dictionary to HashSet (O(1) lookup!)
  2. Create dp array: dp[i] = can segment first i chars
  3. Base case: dp[0] = true (empty string)
  4. For each position i from 1 to n:
     - Try all previous positions j
     - If dp[j]=true AND s[j..i-1] in dictionary
     - Then dp[i] = true
  5. Return dp[n]

Key optimizations:
  - HashSet for O(1) word lookup (CRITICAL!)
  - DP avoids exponential recomputation
  - Early break when segmentation found

Complexity: O(n² × m) time, O(n) space
where n=string length, m=avg word length"

---

🎉 Congratulations!

You've mastered Word Break with the "applepenapple" example!

What You Learned:

✅ String Segmentation - Breaking strings with rules
✅ HashSet Optimization - O(1) lookup is critical
✅ Top-Down vs Bottom-Up - Two valid DP approaches
✅ Forward vs Backward - Different but equivalent
✅ Word Reuse - Simplified problem constraint
✅ Memoization Power - Remember to avoid recomputation

You've mastered a fundamental DP pattern! 🚀✨