TL;DR
Prefix DP: dp[i] = “is s[:i] segmentable”. Bottom-up fill in O(n² · L) time, O(n) space (n = len(s), L = longest word length).
The recurrence
Let dp[i] be True iff the prefix s[:i] (its first i characters) can be split entirely into dictionary words.
dp[0] = True # empty prefix: trivially segmentable
dp[i] = OR over j in [0, i) of ( dp[j] AND s[j:i] in words )
answer = dp[n]
In words: s[:i] works if we can find an earlier cut point j such that everything before j already works and the last chunk s[j:i] is a single dictionary word.
Another way to see it: treat positions 0..n as nodes and draw an edge j → i whenever s[j:i] is a dictionary word. The string is segmentable exactly when a path exists from node 0 to node n. For s = "leetcode", wordDict = ["leet", "code"]:
flowchart LR
n0((0)) -- "leet" --> n4((4))
n4((4)) -- "code" --> n8((8 = n))
Approach 1 — Brute-force recursion
Intuition. Try every dictionary word as the first piece. If some word w is a prefix of the remaining string, recurse on what’s left after w. Succeed if any branch consumes the whole string.
from typing import List
def wordBreak(s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
def can(start: int) -> bool:
if start == len(s): # consumed everything
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in words and can(end):
return True
return False
return can(0)
Complexity: O(2ⁿ · n) time in the worst case (each position either is or isn’t a cut point, and each substring slice costs up to O(n)), O(n) recursion depth. Inputs like s = "aaaa...aab" with wordDict = ["a","aa","aaa",...] re-explore the same suffixes repeatedly, which is why pure recursion times out on these constraints.
Approach 2 — Memoized top-down (add a cache)
can(start) depends only on start: the answer for a given starting index never changes. There are only n+1 distinct starting indices, so caching each one reduces the exponential blowup to n+1 subproblems.
from functools import lru_cache
from typing import List
def wordBreak(s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
max_len = max(map(len, words))
n = len(s)
@lru_cache(maxsize=None)
def can(start: int) -> bool:
if start == n:
return True
# a chunk can be at most max_len long, so stop early
for end in range(start + 1, min(start + max_len, n) + 1):
if s[start:end] in words and can(end):
return True
return False
return can(0)
Walkthrough on s = "leetcode", wordDict = ["leet", "code"] (max_len = 4):
can(0): try "l", "le", "lee" (none in dict), then "leet" ∈ dict → recurse can(4).can(4): try "c", "co", "cod" (none), then "code" ∈ dict → recurse can(8).can(8): start == n → True. Unwinds to True.
Complexity: O(n · L · L) = O(n · L²) time — n cached subproblems, each scans up to L chunk lengths and slices a chunk of length ≤ L. O(n) space for the cache plus recursion stack.
Approach 3 — Tabulated bottom-up
The memoized version fills each index exactly once. Iterating over prefix lengths does the same work without the recursion stack. Here we index by prefix length i (dp[i] covers s[:i]), scanning cut points j from the left.
from typing import List
def wordBreak(s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # empty prefix
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 # one valid split is enough
return dp[n]
Walkthrough on s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]:
i | prefix s[:i] | dp[i] reasoning | dp[i] |
|---|
| 3 | "cat" | dp[0] and "cat" ∈ dict | True |
| 4 | "cats" | dp[0] and "cats" ∈ dict | True |
| 7 | "catsand" | dp[4] and "and" ∈ dict | True |
| 8 | "catsando" | no j with dp[j] and chunk in dict | False |
| 9 | "catsandog" | needs dp[j] with chunk "g"/"og"/… — none work | False |
dp[9] == False → return False. (Note dp[7] is also reachable via dp[3]+"sand", but the suffix "og" is never a word, so the full string still fails.)
Complexity: O(n² · L) time (n prefix ends × up to n cut points × O(L) slice-and-hash), O(n) space. Bounding the inner loop to j >= i - max_len improves it to O(n · L²), matching Approach 2.
Approach 4 — Note on space optimization
The DP is already 1-D and every dp[i] can depend on any earlier dp[j], so you cannot shrink the array to a couple of rolling scalars the way you can for a Fibonacci-style recurrence — O(n) space is the floor here. The realistic further optimization is on time: swap the set for a trie of the dictionary and walk it character by character from each start index, which naturally caps chunk length and avoids building substring slices. Same asymptotics, faster constant factor on large dictionaries.
Common pitfalls
- Forgetting
dp[0] = True; without the empty-prefix base case every dp[i] stays False.
- Using
wordDict as a list and doing in checks against it — that is O(dict) per test and turns the whole thing O(n²·dict·L). Convert to a set once.
- The unbounded inner loop (
for j in range(i)) is correct but wasteful; a chunk longer than max_len can never be a word, so cap it.
- Confusing this with “return all segmentations” (Word Break II) — here you only need a boolean, so
break on the first success.
Pattern takeaway
When a string/array question asks “can it be split so every piece satisfies a rule?”, index a DP by prefix length and let dp[i] mean “the first i characters are valid”. Each new answer combines an earlier answer dp[j] with a check on the single trailing chunk s[j:i]. Seed dp[0] = True for the empty prefix. The recursion, memoization, and tabulation approaches are three views of the same recurrence.