Skip to content

138 — Word Break

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

138 — Word Break

LeetCode 139 · Medium. Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

🍽️ Intuition

Ask, at any prefix of s, "can everything up to here be built from dictionary words?" If the answer is yes for some earlier cut point j, and the remaining chunk from j to the current position is itself a dictionary word, then the answer is yes for the current position too. That's the whole algorithm: s is breakable up to position i if there's some earlier breakable position j where the leftover slice s[j..<i] is a real word. The base case is trivial — the empty prefix (position 0) is trivially "breakable," since there's nothing left to break.

🚩 Pattern-Recognition Cue

"Can this string be segmented into dictionary words" is the cue: a boolean reachability question over string prefixes, where dp[i] ("is the prefix of length i breakable?") depends on whether any earlier breakable prefix dp[j] is followed immediately by a dictionary word covering s[j..<i]. The dictionary/set lookup for "is this slice a word?" is what pulls in a hash set alongside the array.

🐢 Brute Force

Recurse from every position, trying every possible end point for "the next word," with no memoization — the same suffix of s can be reached (and re-checked) through many different earlier split choices.

func wordBreakBruteForce(_ s: String, _ wordDict: [String]) -> Bool {
    let wordSet = Set(wordDict)
    let chars = Array(s)
    let n = chars.count

    func canBreak(_ start: Int) -> Bool {
        if start == n { return true }   // consumed the whole string — success

        for end in (start + 1)...n {
            let word = String(chars[start..<end])
            if wordSet.contains(word) && canBreak(end) {
                return true
            }
        }
        return false
    }

    return canBreak(0)
}

// smoke test
print(wordBreakBruteForce("leetcode", ["leet", "code"]))                          // true
print(wordBreakBruteForce("applepenapple", ["apple", "pen"]))                     // true
print(wordBreakBruteForce("catsandog", ["cats", "dog", "sand", "and", "cat"]))    // false

Big-O: O(2^n · n) time in the worst case — every position can branch into up to n different "next word" end points, and the same later positions get re-explored from many different earlier splits; each branch also pays an O(n) substring extraction. O(n) space for the recursion stack.

🚀 Optimal

Tabulate, for every prefix length from 0 to n, whether that prefix is breakable — a prefix is breakable if some earlier breakable prefix is immediately followed by a dictionary word.

func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    let wordSet = Set(wordDict)
    let chars = Array(s)
    let n = chars.count
    guard n > 0 else { return true }

    var dp = Array(repeating: false, count: n + 1)
    dp[0] = true   // the empty prefix is trivially breakable

    for i in 1...n {
        for j in 0..<i {
            if dp[j] && wordSet.contains(String(chars[j..<i])) {
                dp[i] = true
                break
            }
        }
    }

    return dp[n]
}

// smoke test — same cases as the brute force
print(wordBreak("leetcode", ["leet", "code"]))                          // true
print(wordBreak("applepenapple", ["apple", "pen"]))                     // true
print(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))    // false

Big-O: O(n^3) time — O(n^2) (i, j) prefix pairs, each requiring an O(n) substring extraction to check against the dictionary set. O(n) space for the dp array, plus the space for wordSet.

🔑 The Key Insight

Both versions ask the identical question at every cut point — "does a dictionary word end right here, and is everything before it breakable?" — but the brute force re-derives "is the rest of the string breakable from here?" from scratch every time a position is reached, and the same suffix can be reached through many different earlier word choices, causing exponential re-solving. The optimal version tabulates prefixes left to right instead of suffixes right to left: dp[j] is computed once and then simply looked up (not recomputed) by every later position i that wants to know "was the string breakable up to j?" Turning "is the rest breakable" (recomputed per path) into "was this prefix breakable" (computed once, reused everywhere) is exactly what collapses the exponential search into a polynomial table fill.

🔗 Related Chapters

  • 1D Dynamic Programming — dp[i] depends on a variable number of earlier states (every j < i is a candidate cut point), the same "lookback determined by the problem's structure rather than a fixed window" shape seen in Coin Change.
  • Arrays and Strings — Array(s) and chars[j..<i] slicing back the substring extraction both versions rely on.
  • Hash Maps and Hash Sets — wordSet turns "is this slice a dictionary word?" into an O(1) average-case lookup instead of a linear scan through wordDict.

🧸 Memory Sentence

Word Break is reachability over prefixes — a prefix is breakable the moment some earlier breakable prefix is immediately followed by a real dictionary word, tabulated once per prefix instead of re-derived per path.

✅ Check Your Understanding

  1. Why does dp[0] = true matter as a base case — what would happen to every other dp[i] if it were initialized to false instead?
  2. Trace wordBreak("leetcode", ["leet", "code"]) by hand: which (i, j) pair first sets dp[4] to true, and which pair sets dp[8] to true?
  3. The inner loop breaks as soon as one valid j is found for a given i. Why is it safe to stop searching for more valid j values once dp[i] is known to be true, rather than needing to check every possible split?

⬅️ Previous: Maximum Product Subarray · Next: Longest Increasing Subsequence ➡️

Clone this wiki locally