The O(n) Club: Word Break II — Memoization vs. Recursive Meltdown

The O(n) Club: Word Break II — Memoization vs. Recursive Meltdown

⚡ TL;DR

Split a string into all valid sentences using a dictionary. Brute force recursion is a CPU bonfire; memoization is your fire extinguisher. Quick Java taste:

// Java sanity-saver snippet
List
<string> wordBreak(String s, List<string> wordDict) {
    return helper(s, new HashSet<>(wordDict), new HashMap<>());
}
</string></string>

🧠 How Devs Usually Mess This Up

Classic mistakes in this question:

• Brute force everything — fine for toy inputs, but your recursion stack will soon resemble a Jenga tower at a toddler’s birthday.
• Full-dictionary anagrams — trying every permutation like it’s pre-interview Sudoku. Pro tip: only check string prefixes.
• Forgot to memoize — nothing screams “stuck in recursion limbo” like recomputing the same substring’s splits a hundred times.

🔍 What’s Actually Going On

Your input is a jammed-together sentence. Picture thecatgotachill as a string of fridge magnets. You want to jazz it up by forming all possible sentences, not just one — and not just a boring yes/no like Word Break I. Recursion is obvious, but unless you enjoy Groundhog Day, you must memoize sentence splits for repeating substrings. Otherwise, you’ll burn through call stacks and office coffee. Memoization = remember what you’ve already solved, so you can move on and judge your colleagues instead.

🛠️ PseudoCode

• Throw your words into a HashSet for fast lookups.
  Set<String> dict = new HashSet<>(wordDict);
• Start a fancy memo map to store previously computed splits.
  Map<String, List<String>> memo = new HashMap<>();
• Write a recursive helper:
  • If the substring is empty: return [""] (you’ve finished one sentence — congrats!).
  • If it’s already in your memo, return the stored answer and go take a breath.
  • For every possible prefix:
    • If it’s a valid word, split off and recursively solve the remaining tail.
    • For each result from the tail, prepend the current word (add a space if not empty).
  • Stick it all in your memo and return. Now, go enjoy your less-stressed stack.

💻 The Code

public List<string> wordBreak(String s, List<string> wordDict) {
    return helper(s, new HashSet<>(wordDict), new HashMap<>());
}
 private List
<string> helper(String s, Set<string> dict, Map<string list>> memo) {
    if (memo.containsKey(s)) return memo.get(s);
    List
<string> res = new ArrayList<>();
    if (s.isEmpty()) {
        res.add("");
        return res;
    }
    for (int i = 1; i <= s.length(); i++) {
        String word = s.substring(0, i);
        if (dict.contains(word)) {
            List
<string> sub = helper(s.substring(i), dict, memo);
            for (String tail : sub) {
                res.add(word + (tail.isEmpty() ? "" : " " + tail));
            }
        }
    }
    memo.put(s, res);
    return res;
}
</string></string></string></string></string></string></string>

⚠️ Pitfalls, Traps & Runtime Smacks

• Pathological cases: "aaaaaaa..." + a giant word list = exponential blowup. Don’t expect miracles.
• If you don’t memoize, you’ll “enjoy” computing the same thing until your IDE crashes and your coffee curdles.
• Time/space: Worst case? O(n * 2^n). Yes, for real.
• This is not just Word Break I with sprinkles. You must return every possible sentence split — and sometimes there are far too many.

🧠 Interviewer Brain-Tattoo

Memoization: because “brute-force” is just a fancier word for “infinite loop with regrets.”