The O(n) Club: Word Break — How DP Keeps You From Crying at Your Keyboard

The O(n) Club: Word Break — How DP Keeps You From Crying at Your Keyboard

⚡ TL;DR

Can you cut a string into dictionary words without losing your mind? Yes—if you don’t fall for brute force recursion traps. Do it like this:

// Dynamic programming, because we're not here for exponential time
boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

🧠 How Devs Usually Mess This Up

Ever tried the old “grab the biggest word that fits” routine? Yeah—that greedy hack crashes and burns fast. There are times the shortest chunk is the real MVP. And if you do every lookup using a List instead of a Set, I hope you enjoy O(n³) time and product manager panic. Oh, and if you use BFS/DFS but forget to track visited indices, get ready for your code to run until your next birthday. Seen it. Debugged it. Still have flashbacks.

🔍 What’s Actually Going On

Imagine your string as a mega Subway sandwich, and your only knives (aka words) are whatever the dictionary allows. You want to slice clean, no wasted bread. DP is like keeping a sticky note of every place you’ve already sliced perfectly—so you don’t keep trying to chop where it’s impossible. Greedy would just hack off whatever looks biggest. DP waits, checks its notes, and makes the calculated cut, friend.

🛠️ PseudoCode

• Turn your word list into a set for O(1) lookups.
  Set<String> dict = new HashSet<>(wordDict);
• Set up a boolean dp[] so dp[i] means s[0 to i) can be split.
  boolean[] dp = new boolean[s.length() + 1];<br>dp[0] = true; // empty string is easy
• For i from 1 to s.length():
  Look back at every j before i.
  If dp[j] was true (means we could split s[0:j]) and s.substring(j, i) is in dict, mark dp[i] as true and get out of the inner loop.
• The answer is dp[s.length()] (Was the whole string split or are you just sad?)

💻 The Code

import java.util.*;
 public class WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge cases: Empty string? That’s a yes. Duplicate words in wordDict? Doesn’t matter. Can’t split at all? Prepare for false.
• Lookup speed: Set or bust. Lists will slow you down more than a three-legged turtle.
• Time/space cost: Time: O(n²) because you’re checking every slice. Space: O(n) for dp[]. Still infinitely better than brute-force recursion.
• BFS variant? Mark every position you’ve queued, or you’ll get stuck in endless cycles.
• Real-world fun: Autocorrect splitting ‘therapist’ into ‘the’ and …. well, you get why you need a smart algorithm.

🧠 Interviewer Brain-Tattoo

“If you’re slicing strings like a chef with amnesia, you need DP. Otherwise, enjoy debugging your infinite loop!”