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(W) 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(L) slice + O(L) hash lookup
                return True
        return False
    return f(0)                                   # L5: initial call

def word_break(s, word_dict):
    words = set(word_dict)                        # L1: O(W) 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(L) slice + O(L) 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(W) 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: O(L) slice + lookup
                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(W) 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(L) slice + O(L) hash lookup
                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 = number of words in wordDict, L = max word length.

Line	Per-call cost	Times executed	Contribution
L1 (build set)	$O(W · L)$	1	$O(W · L)$
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(L)$	$O(n)$ per call, $O(2ⁿ)$ calls	$O(2ⁿ · n · L)$ ← dominates
L5 (initial call)	$O(1)$	1	$O(1)$

Without memoization, the same suffix can be recomputed from scratch every time a different prefix reaches it. In the worst case (e.g., s = "aaaaaa", wordDict = ["a", "aa", ...]) the number of distinct recursive calls doubles with each character, producing exponential blowup.

Complexity

Time: $O(2ⁿ)$ , driven by L4 (exponential re-computation of identical subproblems).
Space: $O(n)$ for the call stack.

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(W · L) 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(L) slice + O(L) 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(W · L) 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: O(L) slice + lookup
                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(W · L) 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(L) slice + O(L) hash lookup
                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 = number of words in wordDict, L = max word length.

Line	Per-call cost	Times executed	Contribution
L1 (build set)	$O(W · L)$	1	$O(W · L)$
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(L)$	$O(n²)$ total	$O(n² · L)$ ← dominates
L5 (initial call)	$O(1)$	1	$O(1)$

Memoization limits f to at most n + 1 unique start values. Each unique call does $O(n)$ iterations of the inner loop, each costing $O(L)$ for the slice. Total: $O(n² · L)$ .

Complexity

Time: $O(n² · L)$ , driven by L4 across all memoized calls.
Space: $O(n)$ for the cache and call stack.

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)

dp[i] = True iff s[:i] can be segmented. dp[0] = True; dp[i] = any(dp[j] and s[j:i] in words for j < i).

def word_break(s, word_dict):
    words = set(word_dict)              # L1: O(W · L) 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(L) slice + O(L) 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(W · L) 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: O(L) slice + lookup
                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(W · L) 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(L) slice + O(L) hash lookup
                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] }
}

Where the time goes, line by line

Variables: n = len(s), W = number of words in wordDict, L = max word length.

Line	Per-call cost	Times executed	Contribution
L1 (build set)	$O(W · L)$	1	$O(W · L)$
L2, L3, L4 (init)	$O(n)$ total	1	$O(n)$
L5 (outer loop)	$O(1)$	n	$O(n)$
L6 (inner loop)	$O(1)$	0+1+…+(n-1)	$O(n²)$ iters total
L7 (slice + lookup)	$O(L)$	$O(n²)$ worst case	$O(n² · L)$ ← dominates
L8, L9 (assignments)	$O(1)$	at most n	$O(n)$

The early break in L8 short-circuits once a valid j is found, but the worst case still touches all $O(n²)$ pairs. Each pair costs $O(L)$ for the string slice and hash lookup, giving $O(n² · L)$ overall.

Complexity

Time: $O(n² · L)$ , driven by L7 across all (i, j) pairs.
Space: $O(n)$ for the dp array.

Optimization

Limit the inner loop to j ≥ i - max_word_length. Saves time when dictionary words are short relative to s.

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.

Summary

Approach	Time	Space
Naive recursion	$O(2ⁿ)$	$O(n)$
Top-down memo	$O(n² · L)$	$O(n)$
Bottom-up DP	$O(n² · L)$	$O(n)$

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, $O(1)$ dictionary membership

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.

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)

Optimization

Summary

Test cases

Related data structures

Related concepts