4.23.10 — Word Break

LeetCode 139 · Medium · ★ Blind 75

The problem

Return true if s can be split into a sequence of dictionary words. Words may be reused.

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

String up to 300 characters.

The pattern

The third example is the one that matters. "cats" + "and" leaves "og", which fails. "cat" + "sand" leaves "og", which also fails. A greedy longest-match would commit to "cats" and never try "cat", so greedy is out — a choice now blocks options later, which is the tell for DP.

Let dp[i] mean the first i characters can be fully split.

To decide dp[i], ask where the last word starts. If it starts at j, then two things must hold: the prefix up to j splits (dp[j]), and s[j:i] is a dictionary word.

dp[i] = \text{true if any } j < i \text{ has } dp[j] \ \text{and}\ s[j..i) \in \text{dict}

dp[0] = True — the empty prefix splits trivially, and that base case is what lets the first word be found.

"Where does the last piece start" is the question that produces every string-splitting DP. It is the same question as 4.23.7 Decode Ways, where the piece was 1 or 2 characters. Here it can be any length.

The solution

Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)                        # O(1) lookup
        max_len = max(map(len, wordDict))            # no piece is longer than this

        dp = [False] * (len(s) + 1)
        dp[0] = True                                 # the empty prefix splits

        for i in range(1, len(s) + 1):
            for j in range(max(0, i - max_len), i):  # only plausible start points
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break                            # one split is enough

        return dp[len(s)]

TypeScript

function wordBreak(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict);
  const maxLen = Math.max(...wordDict.map(w => w.length));

  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;

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

  return dp[s.length];
}

A set for the dictionary, so each membership test is O(L) to hash rather than a scan of the whole list.

max(0, i - max_len) is a real optimisation, not decoration. No dictionary word is longer than max_len, so any start point further back cannot produce a valid last word. Without it the inner loop runs i times; with it, at most max_len times. On a 300-character string with short words, that is a large saving.

break on the first success, because you only need to know whether a split exists, not how many.

dp[0] = True is the base case that makes everything work. Without it, no dp[i] could ever become true and the answer would always be false.

Trace

s = "leetcode", dictionary {leet, code}, max_len = 4.

i	prefix	which j works	dp[i]
4	leet	j = 0, dp[0] true and "leet" is a word	true
8	leetcode	j = 4, dp[4] true and "code" is a word	true

Every other i stays false, which is fine — dp[8] is the answer.

The top-down version

from functools import lru_cache

def wordBreak(self, s, wordDict):
    words = set(wordDict)

    @lru_cache(None)
    def can_split(start: int) -> bool:
        if start == len(s):
            return True
        return any(s[start:end] in words and can_split(end)
                   for end in range(start + 1, len(s) + 1))

    return can_split(0)

The cache is what makes it polynomial. Without it, this is exactly the exponential search that fails on inputs like "aaaaaaaaab" with dictionary ["a","aa","aaa",...] — a classic timeout case designed to catch unmemoised recursion.

Complexity

O(n \times \text{max\_len} \times L) where L is the cost of hashing a substring. Usually written as O(n^2) or O(n^3) depending on how the substring cost is counted; be explicit about which you mean rather than saying O(n^2) and hoping.

O(n) space for the table, plus the dictionary.

The trie version

Instead of slicing substrings and hashing them, put the dictionary in a trie (4.15.1). From each start position, walk forward through the trie one character at a time; every time you land on a word-end node, you have found a valid piece.

This avoids building substrings entirely and stops early when no dictionary word continues with the current prefix. Better constants, and it is the version that scales to a large dictionary.

Where this goes next

• Word Break II — return all the sentences, not just whether one exists. That is backtracking with memoisation on the results, and it is the 4.22 dividing line in action: does it exist is DP, list them all is backtracking.
• Palindrome Partitioning — the same splitting with "is a palindrome" instead of "is in the dictionary". 4.18.7.
• Concatenated Words, Extra Characters in a String — same skeleton, different scoring.

The family, one more time: split a string into valid pieces. Fixed lengths → Decode Ways. Dictionary → Word Break. Palindromes → Palindrome Partitioning. Identical structure, different validity test.

What the interviewer will push on

"Why not greedy longest match?" "catsandog". Committing to "cats" blocks the "cat" route, and both fail anyway — but the point is that greedy never explores the alternative.

"What does dp[i] mean?" The first i characters can be split. Say it before writing.

"Why dp[0] = True?" The empty prefix is trivially splittable, and nothing else could ever become true without it.

"How do you avoid scanning every earlier position?" Only look back as far as the longest dictionary word.

"What is the actual complexity?" State the substring cost explicitly.

"What if the dictionary were huge?" A trie, walking forward instead of slicing.

"What if you needed all the sentences?" Word Break II — backtracking with memoisation, and the output can be exponential.

One thing to volunteer: name the question that drives the recurrence — "where does the last word start?" — and point out it is the same question as Decode Ways with a variable piece length. That connection is worth more than the code.

Next: 4.23.11 Longest Increasing Subsequence — the classic O(n^2) DP with a surprising O(n \log n) answer.