How to Solve: Word Break – Complete Guide for FAANG Interviews

How to Solve: Word Break – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can break down complex string problems with dynamic programming, a skill that separates mid-level engineers from senior candidates."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Word Break, ensure you understand: 1. Dynamic Programming (DP) – Memoization and tabulation for optimization. 2. Hash Sets (or Tries) – Fast lookups for dictionary words. 3. Recursion + Backtracking – Breaking problems into smaller subproblems.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Repeatable Checklist)

1. Understand the Problem

• Input: A string s and a dictionary wordDict.
• Output: True if s can be segmented into words from wordDict, else False.
• Edge Cases:
• Empty string → True (if allowed).
• Empty dictionary → False.
• Single-word match → True.

2. Choose the Right Approach

3. Implement DP (Most Common Solution)

1. Define dp[i]: True if s[0:i] can be segmented.
2. Base Case: dp[0] = True (empty string).
3. Transition:
   python
for i in range(1, n+1):
for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
4. Return dp[n].

4. Optimize with BFS (Alternative)

1. Queue stores start indices.
2. For each start, check all possible splits.
3. If a split is valid, enqueue the next start.
4. If end is reached, return True.

5. Handle Follow-Ups

• Follow-up 1: Return all possible segmentations → Use backtracking + memoization.
• Follow-up 2: Count the number of ways → Modify DP to store counts.
• Follow-up 3: Case-insensitive matching → Convert s and wordDict to lowercase.

6. Test Edge Cases

• s = "", wordDict = [] → False (unless empty string allowed).
• s = "a", wordDict = ["a"] → True.
• s = "aaaaaaa", wordDict = ["aaaa", "aaa"] → True.

? WORKED EXAMPLES

Example 1 – Basic (DP)

Problem: s = "leetcode", wordDict = ["leet", "code"] Solution: 1. dp[0] = True (empty string). 2. Check s[0:4] = "leet" → dp[4] = True. 3. Check s[4:8] = "code" → dp[8] = True. 4. Return dp[8].

Code:

def wordBreak(s, wordDict):

    wordSet = set(wordDict)

    n = len(s)

    dp = [False]  (n + 1)

    dp[0] = True  # empty string


    for i in range(1, n + 1):

        for j in range(i):

            if dp[j] and s[j:i] in wordSet:

                dp[i] = True

                break

    return dp[n]

Time: O(n³) (nested loops + substring check). Space: O(n) (DP array).

Why this works: DP breaks the problem into smaller subproblems, avoiding recomputation.

Example 2 – Medium (BFS)

Problem: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Solution: 1. Start at index 0. 2. Check splits: "cat" (valid), "cats" (valid). 3. From "cat", check "sand" (valid), but "og" not in dict → backtrack. 4. From "cats", check "and" (valid), but "og" not in dict → backtrack. 5. No valid path → False.

Code:

from collections import deque

def wordBreak(s, wordDict):

    wordSet = set(wordDict)

    n = len(s)

    queue = deque([0])

    visited = set()


    while queue:

        start = queue.popleft()

        if start == n:

            return True

        if start in visited:

            continue

        visited.add(start)

        for end in range(start + 1, n + 1):

            if s[start:end] in wordSet:

                queue.append(end)

    return False

Time: O(n³) (worst case). Space: O(n) (queue + visited set).

Why this works: BFS explores all possible splits level by level, ensuring the shortest path is found first.

Example 3 – Hard (Follow-Up: All Segmentations)

Problem: Return all possible segmentations of s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]. Solution: 1. Use backtracking + memoization. 2. For each position, try all possible splits. 3. If a split is valid, recurse on the remaining string. 4. Memoize results to avoid recomputation.

Code:

def wordBreak(s, wordDict):

    wordSet = set(wordDict)

    memo = {}


    def backtrack(start):

        if start in memo:

            return memo[start]

        if start == len(s):

            return [""]

        res = []

        for end in range(start + 1, len(s) + 1):

            word = s[start:end]

            if word in wordSet:

                for sentence in backtrack(end):

                    if sentence:

                        res.append(word + " " + sentence)

                    else:

                        res.append(word)

        memo[start] = res

        return res


    return backtrack(0)

Output: ["cat sand dog", "cats and dog"] Time: O(n³) (worst case). Space: O(n²) (memoization).

Why this works: Backtracking explores all valid splits, while memoization prunes redundant computations.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For Word Break, you’ve got three moves: 1. DP is your go-to: dp[i] is True if s[0:i] can be segmented. Loop i from 1 to n, and for each i, check all j < i where dp[j] is True and s[j:i] is in the dictionary. 2. BFS is your backup: If they ask for the shortest path, use a queue to explore splits level by level. 3. Follow-ups? If they want all splits, backtrack + memoize. If the dictionary is huge, build a trie.

Edge cases? Empty string, single-word matches, and large inputs. Optimize with a set for O(1) lookups. Now go crush it—you’ve got this!

? Final Notes

• Practice: LeetCode 139 (Word Break), 140 (Word Break II).
• Time: Aim for 15-20 minutes in an interview.
• Whiteboard: Sketch the DP array or BFS queue before coding.

This framework ensures you never blank on Word Break—just follow the steps, and you’ll solve it systematically. ?