Word Break

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Related Problems
Key Takeaways

📋 Problem Statement

Given a string s and dictionary wordDict, return true if s can be fully segmented into dictionary words.

Examples

Example 1:
Input: s="leetcode", wordDict=["leet","code"]
Output: true

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

🎯 Real-World Analogy

Breaking a Receipt into Known Item Names

You receive one long receipt string like "milkbreadeggs" and need to verify if it can be split into known product names. You mark positions that are reachable by valid splits.

💡 Key Insights

dp[i] means prefix s[:i] can be segmented.
Transition: dp[i] = true if any dp[j] and s[j:i] in dictionary.
Dictionary should be a hash set for O(1) average lookup.
Optional optimization: only check lengths of words in dictionary.

💻 Solution Approaches

Approach 1: DFS Backtracking (No Memo)

Time: Exponential | Space: O(N)

Approach 2: DP Bottom-Up (Recommended)

Time: O(N²) worst case | Space: O(N)

Python Implementation

          from typing import List


def word_break(s: str, word_dict: List[str]) -> bool:
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
      for j in range(i):
        if dp[j] and s[j:i] in words:
          dp[i] = True
          break

    return dp[n]
        

JavaScript Implementation

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

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

  return dp[n];
}
        

🔍 Step-by-Step Walkthrough

Trace s="leetcode", words {"leet","code"}:

dp[0]=true
i=4: j=0 and s[0:4]="leet" -> dp[4]=true
i=8: j=4 and s[4:8]="code" -> dp[8]=true
Final: dp[8]=true

⚡ Complexity Analysis

Time: O(N²) due to two nested indices over the string. Substring extraction cost depends on language runtime implementation.

Space: O(N) for the DP boolean array.

🔧 Edge Cases

Empty string should return true (zero words needed).
Dictionary with repeated words.
String that almost matches but fails near end.
Highly overlapping words like "a", "aa", "aaa".

🧪 Test Cases

Python

def test_word_break():
    assert word_break("leetcode", ["leet", "code"]) is True
    assert word_break("applepenapple", ["apple", "pen"]) is True
    assert word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) is False
    assert word_break("", ["a"]) is True

    print("all tests passed")

JavaScript

function testWordBreak() {
  console.assert(wordBreak("leetcode", ["leet", "code"]) === true, "test 1");
  console.assert(wordBreak("applepenapple", ["apple", "pen"]) === true, "test 2");
  console.assert(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]) === false, "test 3");
  console.assert(wordBreak("", ["a"]) === true, "test 4");

  console.log("all tests passed");
}

💼 Interview Tips

Define the DP state clearly before coding loops.
Mention why pure recursion explodes without memoization.
Show one optimization (word lengths or early breaks).
Be explicit about empty-string behavior.

🎓 Key Takeaways

Word Break is reachability over string indices.
DP + hash set makes segmentation decisions efficient.
Clear state definitions reduce implementation bugs.

← Back to All Algorithms