The O(n) Club: Word Break with Dynamic Programming (No More String-Induced Rage Quits)

The O(n) Club: Word Break with Dynamic Programming (No More String-Induced Rage Quits)

⚡ TL;DR

Can you chop a string into valid dictionary words, using each as many times as your heart desires? Brute force = meltdown. Dynamic programming with a Boolean array = actual job security.

// Do NOT use this unless you hate fast code
boolean wordBreak(String s, List<String> wordDict) {
    // Spoiler: This is glorified recursion hell
    return canBreak(s, new HashSet<>(wordDict));
}

🧠 How Devs Usually Mess This Up

This problem is like repeatedly stubbing your toe on the same bug. Common fails:

• Assume words can’t overlap! They can. Like unlimited buffet visits—hit ’em as many times as you want.
• Bizarre urge to sort the dictionary. If you’re sorting for speed, you’re wasting cycles. HashSet or bust.
• Inner loop checks every single substring? Stop. Only check up to the longest word size. Save your CPU from existential dread.

🔍 What’s Actually Going On

Imagine your string is a long awkward train. You want to see if you can split it into carriages (words) borrowed from your dictionary—a library where you’re totally allowed to re-borrow the same carriage 1000 times. For each position in the string, keep a little “yes/no” tag: up to here, is it possible to cut the string cleanly?

The trick: for each substring ending at position i, try all possible previous splits j where the left part is valid (dp[j] == true), and the word s[j...i-1] is in your set. If yes—slap a “true” on dp[i] and call it a day for that index.

🛠️ PseudoCode

• Convert wordDict to a Set for instant lookups:
  

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

• Find the maximum dictionary word length:
  

  int maxLen = wordDict.stream().mapToInt(String::length).max().orElse(0);

• Use a dp[] array, set dp[0] = true:
  

  boolean[] dp = new boolean[s.length() + 1];
  dp[0] = true;

• For i = 1 to s.length(), test substrings ending at i of only feasible lengths:
  

  for (int i = 1; i <= s.length(); i++) {
      for (int j = Math.max(0, i - maxLen); j < i; j++) {
          if (dp[j] && wordSet.contains(s.substring(j, i))) {
              dp[i] = true;
              break;
          }
      }
  }

• Final result: dp[s.length()]—Can the whole string be segmented?

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty string? Always breakable. Empty dict? You’re out of luck. Don’t be fooled.
• Monster inputs? If s or wordDict is monstrous, mind your memory—your laptop will let you know.
• Ignoring max word length: If you don’t throttle that inner loop, your code will run like a 1997 dial-up.
• Time: Roughly O(n*m), n = string length, m = max word size you actually care about.
• Space: O(n + d); n for dp[], d for wordSet. Reasonable unless you hate free RAM.

🧠 Interviewer Brain-Tattoo

Word Break is secretly a test: will you brute-force your way to tears, or build a DP table like a civilized coder? Use your RAM. Break the string, not your spirit.