140. Word Break II — DSA Atlas

140

HardOne-Dimensional Dynamic ProgrammingBacktracking plus memoization (top-down DP)DFS with memoized suffix enumeration

Word Break II

Given a string s and a dictionary wordDict, return all possible sentences where s is segmented into a space-separated sequence of dictionary words. Words may be reused. Return the sentences in any order.

Open official problem prompt ↗

In plain English

Produce every full segmentation of s into dictionary words as readable sentences.

Picture it like this

Listing all the different routes through a city where each road segment is a dictionary word - you enumerate paths, caching the routes from each intersection you have already explored.

Example

Input: s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
Output: ["cats and dog", "cat sand dog"]
Why: Both "cats|and|dog" and "cat|sand|dog" tile the string using dictionary words.

Constraints

1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s and wordDict[i] consist of only lowercase English lettersAll dictionary words are uniqueThe answer may contain up to 10^4 sentences

Pattern lesson

See the pattern, then code

DFS with memoized suffix enumeration

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. The set of sentences for the suffix starting at index i is: for every dictionary word beginning at i, that word joined with every sentence produced from the suffix after it.

New words, made simpleKnow these before the algorithm

Suffix result: All sentences that segment the part of s starting at a given index.
Memoization: Caching dfs(start) so shared suffixes are computed only once.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Pure backtracking

Wastes work when many prefixes share the same tail.

DFS building sentences, recomputing each suffix every time it is reached.

Time Exponential with heavy repetitionSpace O(n)

Best choiceMemoized DFS

Avoids recomputing suffixes while still emitting every sentence.

Cache the list of sentences for each start index and reuse it.

Time O(n^2) matching plus output sizeSpace O(n * output)

The rule we keep true

Invariant

dfs(start) returns exactly the set of valid segmentations of s[start:], each as a space-joined string.

Why this is correct

Reasoning

Every sentence for s[start:] is a first dictionary word s[start:end] followed by some sentence for s[end:]; iterating all valid first words and combining with the recursively complete tail set yields all sentences without duplication.

The algorithm in three movesSay these aloud before coding

1Store the dictionary in a set

dfs(7)=['dog']

2Define dfs(start) returning all sentence tails for s[start:]

dfs(4)=['and dog']

3Base case: at end return a list with one empty string

dfs(0)=['cats and dog','cat sand dog']

4For each end where s[start:end] is a word, prepend it to each tail from dfs(end)

5Memoize dfs(start) so overlapping suffixes are solved once

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

cats0

and1

dog2

1 · Reads[7:]='dog'

2 · AskWords starting at 7?

3 · Update state'dog' matches, tail dfs(10)=['']

4 · Resultreturns ['dog']

Key takeaway

One valid tiling: 'cats' + 'and' + 'dog' reconstructed from memoized suffix results.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Setup
Dictionary set for lookups and a memo keyed by start index.
2
Lines 6-8Base and cache hit
Reaching the end yields one empty tail; a cached start returns immediately.
3
Lines 10-16Enumerate first words
For each valid leading word, join it to every tail sentence from the recursive call.
4
Lines 18Kick off
dfs(0) returns all sentences for the whole string.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No valid segmentation returns an empty list
A word that is a prefix of another (cat/cats) creates multiple branches
Reused words across the sentence
Single-word strings return that one word

Common beginner mistakes

Joining the empty tail with a stray trailing space - guard the base case
Forgetting to memoize, causing timeouts on adversarial inputs like many 'a's
Storing indices in memo but returning mutated shared lists

Check your understanding

Why return [""] rather than [] at the end of the string?

PyPython 3 · solution.py

Optimal

1class Solution:2    def wordBreak(self, s: str, wordDict: list[str]) -> list[str]:3        words = set(wordDict)4        memo: dict[int, list[str]] = {}56        def dfs(start: int) -> list[str]:7            if start == len(s):8                return [""]9            if start in memo:10                return memo[start]11            res = []12            for end in range(start + 1, len(s) + 1):13                word = s[start:end]14                if word in words:15                    for tail in dfs(end):16                        res.append(word if tail == "" else word + " " + tail)17            memo[start] = res18            return res1920        return dfs(0)

Time complexityO(n^2 + n * k) where k is the number of valid sentencesOptimized

Space complexityO(n * k) for memoized sentence listsExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonMetaUber

Word Break II

Word Break II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming