227. Word Break

Why this mechanism works

Let dp[i] mean the prefix ending before i is segmentable. To set it true, find an earlier reachable cut start whose following substring is a dictionary word. Bound candidate word length by the dictionary's longest word to avoid checking impossible long pieces.

State and boundaries

dp[i] is true exactly when text[:i] can be segmented. dp[0] is the reachable empty prefix.

Protocol

1. Build a set of nonempty words and their maximum length.
2. Set dp[0]=true.
3. For each end, try eligible earlier starts.
4. If dp[start] and text[start:end] is a word, mark end and stop its search.
5. Return dp[n].

Visualization

text 'leetcode', dictionary {leet,code}
dp[0]=true -> dp[4]=true via 'leet'
dp[4]=true -> dp[8]=true via 'code'

Python implementation

def word_break(text, dictionary):
    words = {word for word in dictionary if word}
    limit = min(len(text), max(map(len, words), default=0))
    dp = [False] * (len(text) + 1)
    dp[0] = True
    for end in range(1, len(text) + 1):
        for start in range(max(0, end - limit), end):
            if dp[start] and text[start:end] in words:
                dp[end] = True
                break
    return dp[-1]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 word_break: words = {word for word in dictionary if word}
text='leetcode'; dictionary=['leet', 'code']; word='leet'

L2 word_break: words = {word for word in dictionary if word}
text='leetcode'; dictionary=['leet', 'code']; word='code'

L2 word_break: words = {word for word in dictionary if word}
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}

L3 word_break: limit = min(len(text), max(map(len, words), default=0))
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4

L4 word_break: dp = [False] * (len(text) + 1)
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4; dp=[False, False, False, False, False, False, False, False, ...]

L5 word_break: dp[0] = True
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4; dp=[True, False, False, False, False, False, False, False, ...]

L6 word_break: for end in range(1, len(text) + 1):
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4; dp=[True, False, False, False, False, False, False, False, ...]; end=1

L7 word_break: for start in range(max(0, end - limit), end):
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4; dp=[True, False, False, False, False, False, False, False, ...]; end=1; start=0

... 22 intermediate state changes omitted ...

L7 word_break: for start in range(max(0, end - limit), end):
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4; dp=[True, False, False, False, True, False, False, False, ...]; end=7; start=5

L7 word_break: for start in range(max(0, end - limit), end):
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4; dp=[True, False, False, False, True, False, False, False, ...]; end=7; start=6

L6 word_break: for end in range(1, len(text) + 1):
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4; dp=[True, False, False, False, True, False, False, False, ...]; end=8; start=6

L7 word_break: for start in range(max(0, end - limit), end):
text='leetcode'; dictionary=['leet', 'code']; words={'code', 'leet'}; limit=4; dp=[True, False, False, False, True, False, False, False, ...]; end=8; start=4

L2 word_break: words = {word for word in dictionary if word}
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; word='cats'

L2 word_break: words = {word for word in dictionary if word}
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; word='dog'

L2 word_break: words = {word for word in dictionary if word}
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; word='sand'

L2 word_break: words = {word for word in dictionary if word}
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; word='and'

L2 word_break: words = {word for word in dictionary if word}
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; word='cat'

L2 word_break: words = {word for word in dictionary if word}
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; words={'and', 'cat', 'cats', 'dog', 'sand'}

L3 word_break: limit = min(len(text), max(map(len, words), default=0))
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; words={'and', 'cat', 'cats', 'dog', 'sand'}; limit=4

L4 word_break: dp = [False] * (len(text) + 1)
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; words={'and', 'cat', 'cats', 'dog', 'sand'}; limit=4; dp=[False, False, False, False, False, False, False, False, ...]

... 29 intermediate state changes omitted ...

L7 word_break: for start in range(max(0, end - limit), end):
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; words={'and', 'cat', 'cats', 'dog', 'sand'}; limit=4; dp=[True, False, False, True, True, False, False, True, ...]; end=9; start=5

L7 word_break: for start in range(max(0, end - limit), end):
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; words={'and', 'cat', 'cats', 'dog', 'sand'}; limit=4; dp=[True, False, False, True, True, False, False, True, ...]; end=9; start=6

L7 word_break: for start in range(max(0, end - limit), end):
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; words={'and', 'cat', 'cats', 'dog', 'sand'}; limit=4; dp=[True, False, False, True, True, False, False, True, ...]; end=9; start=7

L7 word_break: for start in range(max(0, end - limit), end):
text='catsandog'; dictionary=['cats', 'dog', 'sand', 'and', 'cat']; words={'and', 'cat', 'cats', 'dog', 'sand'}; limit=4; dp=[True, False, False, True, True, False, False, True, ...]; end=9; start=8

Why the solution is correct

Any successful transition appends a valid word to a valid prefix, so it constructs a segmentation. Conversely, the final word of any segmentation begins at a reachable earlier cut examined by the loop. The maximum-length bound cannot remove a dictionary word. Induction over end proves every state exact.

Time and space

O(n*L^2+S) worst-case Python time, including substring creation/hashing, for maximum relevant word length L<=n and total dictionary characters S; O(n+S) storage. Without slicing costs the transition count is O(n*L).

Common mistakes

A greedy longest-word choice can block a later valid segmentation. Claiming O(n^2) while repeatedly creating length-O(n) substrings overlooks Python's copying cost.

Reasoning card

Transfer exercise

Use a trie to scan forward from reachable cuts, avoiding substring allocation at every candidate boundary.