Word Break Solution

Problem

Given a string and a list of valid words, determine whether the string can be split into a sequence of one or more words where every word comes from the list. Words from the list can be reused any number of times.

Example:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leet" + "code" covers the entire string.

Counter-example (greedy fails): With s = "cars" and wordDict = ["car", "ca", "rs"], a greedy approach (always matching the longest prefix) picks "car" and leaves "s" unsegmentable. The correct split is "ca" + "rs". This is why backtracking or dynamic programming is needed.

Intuition

The problem is really asking: can we place cut-marks at some positions in the string so that every resulting piece is a dictionary word? The key observation is that whether position i is reachable depends only on whether some earlier position j is reachable and s[j:i] is a valid word. That single-directional dependency is the hallmark of 1D dynamic programming — compute and cache results from left to right, using each earlier result at most once per future position.

Approach 1 — Brute Force Recursion

At each index, try every dictionary word that starts there. If the word matches, recurse on the remaining suffix. Without memoization, overlapping subproblems are recomputed exponentially.

Steps:

Build a set from wordDict for O(1) membership checks.
Define a recursive function that takes the current start index.
Base case: if start == len(s), the entire string has been segmented — return True.
For each possible end position, check if s[start:end] is in the word set.
If a match is found, recurse on end; return True if that recursion succeeds.
If no match leads to a full segmentation, return False.

1def wordBreak(s: str, wordDict: list[str]) -> bool:
2    word_set = set(wordDict)
3
4    def can_segment(start: int) -> bool:
5        if start == len(s):
6            return True  # consumed the entire string successfully
7        for end in range(start + 1, len(s) + 1):
8            if s[start:end] in word_set and can_segment(end):
9                return True
10        return False
11
12    return can_segment(0)

Time: O(2^n) — at each of n characters, we branch on whether to cut here or not; without caching, exponentially many paths are re-explored
Space: O(n) — the recursion stack can go n levels deep in the worst case

Approach 2 — Bottom-Up Dynamic Programming

Build a boolean array dp where dp[i] means the prefix s[:i] can be segmented using dictionary words. Fill it left to right, using previously computed entries.

Steps:

Convert wordDict to a hash set for O(1) lookups.
Allocate dp of size n + 1, all False; set dp[0] = True (empty prefix is trivially segmentable).
For each end position from 1 to n (inclusive):
Scan every start position from 0 to end − 1.
If dp[start] is True and s[start:end] is in the word set, mark dp[end] = True and stop scanning.
Return dp[n].

1def wordBreak(s: str, wordDict: list[str]) -> bool:
2    word_set = set(wordDict)
3    n = len(s)
4    dp = [False] * (n + 1)
5    dp[0] = True  # empty prefix is trivially segmentable
6
7    for end in range(1, n + 1):
8        for start in range(end):
9            if dp[start] and s[start:end] in word_set:
10                dp[end] = True
11                break  # found a valid split; no need to check other start positions
12
13    return dp[n]

Time: O(n²) — two nested loops over the string length; each substring hash takes O(k) where k is substring length, making the theoretical worst case O(n³), but O(n²) when dictionary word lengths are bounded
Space: O(n + M) — dp array of size n + 1 plus the hash set holding M total characters from the dictionary

Complexity Summary

Approach	Time	Space	When to use
Brute Force Recursion	O(2^n)	O(n)	Never in production; useful only to understand why caching is necessary
Bottom-Up DP	O(n²)	O(n + M)	Always — iterative, no stack overflow risk, directly readable state table

Common Mistakes

Forgetting dp[0] = True: The entire chain depends on this anchor. Without it, dp[start] is never True, so no dp[end] can ever be set to True — the function always returns False.
Allocating dp of size n instead of n + 1: The answer lives at dp[n], so the array must hold indices 0 through n inclusive; off-by-one here causes an index-out-of-bounds error.
Checking s[start:end] in wordDict against the original list instead of a set: List membership is O(k) per call where k is the number of words; converting to a set once at the start reduces each lookup to O(1) amortized.
Trusting greedy matching: Always picking the longest prefix that is a valid word fails whenever a shorter first word is the only path to a full segmentation. The DP naturally handles all splits simultaneously — greedy picks just one.
Skipping the dp[start] check: Marking dp[end] = True whenever s[start:end] is a word (without verifying dp[start]) is wrong — position start must itself be reachable before we can extend from it.

Word Break — Solution