139. Word Break (Medium)

Problem

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.

Example

s = "leetcode", wordDict = ["leet", "code"] → true
s = "applepenapple", wordDict = ["apple", "pen"] → true
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] → false

LeetCode 139 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recursive, try every prefix

def word_break(s, word_dict):
    words = set(word_dict)                        # L1: O(D) to build set
    def f(start):
        if start == len(s):                       # L2: base case, O(1)
            return True
        for end in range(start + 1, len(s) + 1): # L3: try every prefix from start
            if s[start:end] in words and f(end):  # L4: O(end - start) slice + hash lookup
                return True
        return False
    return f(0)                                   # L5: initial call

function wordBreak(s: string, wordDict: string[]): boolean {
    const words = new Set(wordDict);                       // L1: O(D) to build set
    function f(start: number): boolean {
        if (start === s.length) return true;               // L2: base case, O(1)
        for (let end = start + 1; end <= s.length; end++) { // L3: try every prefix
            if (words.has(s.slice(start, end)) && f(end)) { // L4: substring creation and hashing
                return true;
            }
        }
        return false;
    }
    return f(0);                                           // L5: initial call
}

func wordBreak(s string, wordDict []string) bool {
    words := map[string]bool{}
    for _, w := range wordDict {
        words[w] = true                                    // L1: O(D) to build set
    }
    var f func(start int) bool
    f = func(start int) bool {
        if start == len(s) {                               // L2: base case, O(1)
            return true
        }
        for end := start + 1; end <= len(s); end++ {      // L3: try every prefix from start
            if words[s[start:end]] && f(end) {             // L4: O(end-start) hashing, O(1) slice
                return true
            }
        }
        return false
    }
    return f(0)                                            // L5: initial call
}

final class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool { let c = Array(s), words = wordDict.map(Array.init); func solve(_ i: Int) -> Bool { if i == c.count { return true }; for word in words where i + word.count <= c.count { if Array(c[i..<(i + word.count)]) == word && solve(i + word.count) { return true } }; return false }; return solve(0) }
}

Where the time goes, line by line

Variables: n = len(s), W = word count, D = total dictionary characters, L = max word length.

Line	Per-call cost	Times executed	Contribution
L1 (build set)	$O(D)$	1	$O(D)$
L2 (base case)	$O(1)$	once per call	$O(calls)$
L3 (range loop)	$O(n)$ iterations	once per call	$O(n · calls)$
L4 (slice + lookup)	$O(n)$ upper bound	$O(n)$ per call, $O(2^n)$ calls	$O(n^2 2^n)$ coarse upper bound
L5 (initial call)	$O(1)$	1	$O(1)$

Without memoization, different segmentations can reach the same suffix and recompute it. A run of "a" characters ending in "b", with dictionary words covering many lengths of "a", forces repeated failed branches. There are at most $O(2^n)$ calls, each trying up to n endpoints with up to n characters of substring work. This gives a deliberately coarse exponential upper bound.

Complexity

Time: $O(D + n^2 2^n)$ as a coarse upper bound including substring work. Memoization removes the repeated subproblems.
Space: $O(n + W)$ for the call stack, word-set entries, and a temporary substring. Recursion passes indices rather than suffix copies.

Approach 2: Top-down memoized

Cache by start index.

from functools import lru_cache

def word_break(s, word_dict):
    words = set(word_dict)                        # L1: O(D) to build set
    @lru_cache(maxsize=None)
    def f(start):
        if start == len(s):                       # L2: base case, O(1)
            return True
        for end in range(start + 1, len(s) + 1): # L3: try every split point
            if s[start:end] in words and f(end):  # L4: O(end - start) slice + hash lookup
                return True
        return False
    return f(0)                                   # L5: initial call

function wordBreak(s: string, wordDict: string[]): boolean {
    const words = new Set(wordDict);                       // L1: O(D) to build set
    const memo = new Map<number, boolean>();
    function f(start: number): boolean {
        if (start === s.length) return true;               // L2: base case, O(1)
        if (memo.has(start)) return memo.get(start)!;
        for (let end = start + 1; end <= s.length; end++) { // L3: try every split point
            if (words.has(s.slice(start, end)) && f(end)) { // L4: substring creation and hashing
                memo.set(start, true);
                return true;
            }
        }
        memo.set(start, false);
        return false;
    }
    return f(0);                                           // L5: initial call
}

func wordBreak(s string, wordDict []string) bool {
    words := map[string]bool{}
    for _, w := range wordDict {
        words[w] = true                                    // L1: O(D) to build set
    }
    memo := map[int]bool{}
    var f func(start int) bool
    f = func(start int) bool {
        if start == len(s) {                               // L2: base case, O(1)
            return true
        }
        if v, ok := memo[start]; ok {
            return v
        }
        for end := start + 1; end <= len(s); end++ {      // L3: try every split point
            if words[s[start:end]] && f(end) {             // L4: O(end-start) hashing, O(1) slice
                memo[start] = true
                return true
            }
        }
        memo[start] = false
        return false
    }
    return f(0)                                            // L5: initial call
}

final class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool { let c = Array(s), words = wordDict.map(Array.init); var memo: [Int: Bool] = [:]; func solve(_ i: Int) -> Bool { if i == c.count { return true }; if let value = memo[i] { return value }; for word in words where i + word.count <= c.count { if Array(c[i..<(i + word.count)]) == word && solve(i + word.count) { memo[i] = true; return true } }; memo[i] = false; return false }; return solve(0) }
}

Where the time goes, line by line

Variables: n = len(s), W = word count, D = total dictionary characters, L = max word length.

Line	Per-call cost	Times executed	Contribution
L1 (build set)	$O(D)$	1	$O(D)$
L2 (base case)	$O(1)$	at most n + 1	$O(n)$
L3 (range loop)	$O(n)$ iterations	n unique start values	$O(n²)$ total iters
L4 (slice + lookup)	$O(n)$ upper bound	$O(n²)$ total	$O(n³)$ ← dominates
L5 (initial call)	$O(1)$	1	$O(1)$

Memoization limits f to at most n + 1 unique start values. Each call tries up to $O(n)$ endpoints. In Python, the unrestricted slices and their hashes can each cost $O(n)$ , so this implementation has an $O(n^3)$ upper bound, plus dictionary setup.

Complexity

Time: $O(D + n^3)$ , including dictionary setup and unrestricted Python slicing and hashing.
Space: $O(n + W)$ for cache entries, stack, set entries, and the temporary candidate substring. Recursion passes indices rather than copying suffix strings.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Bottom-up DP (canonical)

def word_break(s, word_dict):
    words = set(word_dict)              # L1: O(D) to build set
    n = len(s)                          # L2: O(1)
    dp = [False] * (n + 1)             # L3: O(n) allocation
    dp[0] = True                        # L4: base case, O(1)
    for i in range(1, n + 1):          # L5: outer loop, n iterations
        for j in range(i):             # L6: inner loop, i iterations
            if dp[j] and s[j:i] in words:  # L7: O(i - j) slice + hash lookup
                dp[i] = True           # L8: O(1)
                break
    return dp[n]                        # L9: O(1)

function wordBreak(s: string, wordDict: string[]): boolean {
    const words = new Set(wordDict);              // L1: O(D) to build set
    const n = s.length;                           // L2: O(1)
    const dp = new Array(n + 1).fill(false);      // L3: O(n) allocation
    dp[0] = true;                                 // L4: base case, O(1)
    for (let i = 1; i <= n; i++) {               // L5: outer loop, n iterations
        for (let j = 0; j < i; j++) {            // L6: inner loop, i iterations
            if (dp[j] && words.has(s.slice(j, i))) {  // L7: substring creation and hashing
                dp[i] = true;                    // L8: O(1)
                break;
            }
        }
    }
    return dp[n];                                 // L9: O(1)
}

func wordBreak(s string, wordDict []string) bool {
    words := map[string]bool{}
    for _, w := range wordDict {
        words[w] = true                           // L1: O(D) to build set
    }
    n := len(s)                                   // L2: O(1)
    dp := make([]bool, n+1)                       // L3: O(n) allocation
    dp[0] = true                                  // L4: base case, O(1)
    for i := 1; i <= n; i++ {                    // L5: outer loop, n iterations
        for j := 0; j < i; j++ {                 // L6: inner loop, i iterations
            if dp[j] && words[s[j:i]] {           // L7: O(i-j) hashing, O(1) slice
                dp[i] = true                      // L8: O(1)
                break
            }
        }
    }
    return dp[n]                                  // L9: O(1)
}

final class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool { let c = Array(s), words = wordDict.map(Array.init); var dp = Array(repeating: false, count: c.count + 1); dp[c.count] = true; for i in stride(from: c.count - 1, through: 0, by: -1) { for word in words where i + word.count <= c.count && Array(c[i..<(i + word.count)]) == word { if dp[i + word.count] { dp[i] = true; break } } }; return dp[0] }
}

State: what does each slot mean?

dp[i] means the first i characters can be segmented into dictionary words. It does not mean that the entire prefix must itself be one dictionary word.

For s = "leetcode" and word_dict = ["leet", "code"]:

Prefix length:  0   1   2   3    4     5      6       7        8
Prefix:         ""  l   le  lee  leet  leetc  leetco  leetcod  leetcode
dp:             T   F   F   F    T     F      F       F        T

There are n + 1 slots because prefix lengths run from 0 through n. dp[0] = True is the valid empty prefix: it supplies a starting point for the first dictionary word. This is the prefix-length DP convention.

What each part of the code does

Code	Meaning
`words = set(word_dict)`	Build a membership structure for whole dictionary words. `dict(word_dict)` would expect key-value pairs.
`dp = [False] * (n + 1)`	Reserve one slot for every prefix length, including zero.
`dp[0] = True`	Mark the empty prefix as valid so the first word can begin at index `0`.
`for i in range(1, n + 1)`	Choose the endpoint of the prefix being solved.
`for j in range(i)`	Try each starting position for its final word.
`dp[j]`	Check whether everything before the split is already segmentable.
`s[j:i] in words`	Check whether the entire final piece is one dictionary word. `s[i - 1]` alone would inspect only one character.
`dp[i] = True`	Record that a valid split was found.
`break`	Stop searching: this is a feasibility question, so one valid split is enough.
`return dp[n]`	Return whether the entire string can be segmented.

Concrete transitions: a valid prefix plus one last word

At i = 4, the split j = 0 works:

Already valid prefix: ""       dp[0] = True
Last word:            "leet"   s[0:4] in words
Result:                        dp[4] = True

At i = 8, the split j = 4 works:

Character index:   0 1 2 3   4 5 6 7
s:                 l e e t | c o d e |
Split position:           j=4       i=8

Already valid prefix: "leet"   dp[4] = True
Last word:            "code"   s[4:8] in words
Result:                        dp[8] = True

The reusable rule is a valid earlier prefix plus one valid final piece makes a valid larger prefix. Both checks must hold for the same split j. A dictionary word at the end cannot repair an invalid earlier prefix: "xcode" is false with ["leet", "code"], even though "code" is a word.

Python’s and skips the substring check when dp[j] is false. Words remain in the set after use, so "applepenapple" can use "apple" twice. The loop considers all possible splits rather than committing to the first word that looks plausible.

Where the time goes, line by line

Let n = len(s), W be the number of dictionary words, and D be their total character count. These Python bounds account for creating and hashing new substrings under average hash-table behavior.

Line	Work	Cost
L1	Build the word set, including initial word hashing.	$O(D)$
L2-L4	Read the length, allocate the DP table, and set its base case.	$O(n)$
L5-L6	Try split positions for every endpoint.	At most `1 + 2 + ... + n` pairs, or $O(n^2)$
L7	If `dp[j]` is true, create and hash `s[j:i]`.	$O(i-j)$ per checked substring, up to $O(n)$
L8	Set a feasible state and stop its inner loop.	At most once per endpoint, $O(n)$ total
L9	Read the final state.	$O(1)$

Complexity: The unrestricted version takes $O(D + n^3)$ worst-case time, not merely $O(n^2)$ : counting split pairs alone omits substring creation and hashing. An early break can help individual inputs but does not remove that worst case. It uses $O(n + W)$ auxiliary space for the DP table, set entries referencing the existing words, and one temporary substring of up to length n. If dictionary character storage is counted too, the bound is $O(n + D)$ .

The maximum dictionary-word length does not bound the substrings created by this code: the unrestricted loop still constructs candidates that are too long to match. The final version below avoids that wasted work.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Final version: bound the last word’s length

Keep the same state, base case, and two checks. Only the candidate split range changes. If the longest dictionary word has length L, a substring longer than L cannot match a word, so there is no reason to construct it.

def word_break_bounded(s: str, word_dict: list[str]) -> bool:
    words = set(word_dict)
    max_len = max(len(word) for word in words)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

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

    return dp[n]

The problem guarantees a nonempty dictionary of nonempty words, so max has at least one value. A valid final word starts no earlier than i - max_len. Clamping that start to 0 avoids negative positions near the beginning of the string. Every valid segmentation considered by the original version is still reachable.

Complexity discussion

Let L be the longest dictionary-word length and K = min(n, L). The optimized version considers at most K splits per endpoint, for $O(nK)$ candidates. Each new substring has at most K characters, so slicing and hashing cost at most $O(K)$ . Total time is $O(D + nK^2)$ , commonly written $O(D + nL^2)$ when L <= n. Computing max_len takes $O(W)$ , absorbed by $O(D)$ because dictionary words are nonempty.

For this problem, L <= 20. That bounds the substring work at each endpoint, so the optimized scan is linear in n when treating the maximum word length as a fixed constant, plus dictionary setup. Without the length cap, the baseline has $O(n^2)$ candidate splits and up to $O(n)$ substring work per candidate, hence $O(D + n^3)$ .

The optimized implementation uses $O(n + W)$ auxiliary space: the DP table, word-set references, and one temporary substring of up to K characters. Counting the input word characters as stored dictionary data gives $O(n + D)$ instead. A set lookup has average constant-time table probing, but hashing a newly created string still takes time proportional to its length.

This remains prefix DP. Word Break can depend on any valid earlier split within the word-length window, so the two-variable optimization from Climbing Stairs and House Robber cannot be copied directly.

Summary

Python costs below include dictionary setup. D is total dictionary characters, W is word count, and L is maximum word length. The naive recursion row is a coarse upper bound that includes substring work.

Approach	Time	Space
Naive recursion	$O(D + n^2 2^n)$ coarse upper bound	$O(n + W)$
Top-down memo	$O(D + n^3)$ upper bound	$O(n + W)$
Bottom-up DP	$O(D + n^3)$	$O(n + W)$
Length-bounded bottom-up DP	$O(D + nK^2)$ , `K = min(n, L)`	$O(n + W)$

The “partition a string into dictionary pieces” template applies to Word Break II (140, which enumerates all segmentations) and Concatenated Words (472).

Test cases

# Quick smoke tests, paste into a REPL or save as test_word_break.py and run.
# Uses the canonical implementation (Approach 3: bottom-up DP).

def word_break(s, word_dict):
    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]

def _run_tests():
    # LeetCode examples
    assert word_break("leetcode", ["leet", "code"]) == True
    assert word_break("applepenapple", ["apple", "pen"]) == True
    assert word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) == False
    # Edge cases
    assert word_break("a", ["a"]) == True
    assert word_break("a", ["b"]) == False
    # Word reuse
    assert word_break("aaaa", ["a", "aa"]) == True
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function wordBreak(s: string, wordDict: string[]): boolean {
    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++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && words.has(s.slice(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

console.assert(wordBreak('leetcode', ['leet', 'code']) === true);
console.assert(wordBreak('applepenapple', ['apple', 'pen']) === true);
console.assert(wordBreak('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']) === false);
console.assert(wordBreak('a', ['a']) === true);
console.assert(wordBreak('a', ['b']) === false);
console.assert(wordBreak('aaaa', ['a', 'aa']) === true);
console.log('all tests pass');

package main

import "fmt"

func assert(condition bool, msgs ...string) {
  if !condition {
    msg := "assertion failed"
    if len(msgs) > 0 {
      msg = msgs[0]
    }
    panic(msg)
  }
}

func wordBreak(s string, wordDict []string) bool {
  words := map[string]bool{}
  for _, w := range wordDict {
    words[w] = true
  }
  n := len(s)
  dp := make([]bool, n+1)
  dp[0] = true
  for i := 1; i <= n; i++ {
    for j := 0; j < i; j++ {
      if dp[j] && words[s[j:i]] {
        dp[i] = true
        break
      }
    }
  }
  return dp[n]
}

func runTests() {
  assert(wordBreak("leetcode", []string{"leet", "code"}))
  assert(wordBreak("applepenapple", []string{"apple", "pen"}))
  assert(!wordBreak("catsandog", []string{"cats", "dog", "sand", "and", "cat"}))
  assert(wordBreak("a", []string{"a"}))
  assert(!wordBreak("a", []string{"b"}))
  assert(wordBreak("aaaa", []string{"a", "aa"}))
  fmt.Println("all tests pass")
}

func main() { runTests() }

Strings, prefix DP
Hash Tables, average constant-time table probing after hashing the candidate word

Memoization, top-down caching tactics for preserving recursive clarity while avoiding repeated subproblem work.
Sequence DP, order-aware DP tactics for strings and arrays where prefixes or positions define reusable states.
Tabulation: prefix-length DP, one Boolean state per prefix and a valid empty prefix.

139. Word Break (Medium)

Problem

Try it yourself

Approach 1: Recursive, try every prefix

Approach 2: Top-down memoized

Approach 3: Bottom-up DP (canonical)

State: what does each slot mean?

What each part of the code does

Concrete transitions: a valid prefix plus one last word

Final version: bound the last word’s length

Complexity discussion

Summary

Test cases

Related data structures

Related concepts