LeetCode 139 · 1-D DP

Word Break, explained with a picture

Snapping word tiles onto a sentence strip.

Medium1-D DP
▶ Watch it step by step

The problem

Given a string and a list of dictionary words, decide whether the string can be split into a sequence of dictionary words (words may be reused).

Input:  s = "leetcode", words = ["leet", "code"]
Output: true

Picture it

Picture a strip of letters and a set of word tiles. We mark each position on the strip “reachable” if the letters before it can be completely covered with tiles. Position 0 is reachable. From any reachable position, if a tile matches the next letters, the position after that tile becomes reachable too. The question is whether the end of the strip becomes reachable.

How to recognise it

  • You must decide whether a string can be cut into pieces that all come from a given list, with pieces reusable.
  • A cut at position i only matters through one question: "can the first i letters be split?" That answer is reused by every later cut.
  • The string has at most 300 letters and the dictionary up to 1,000 words of up to 20 letters, so trying every split is hopeless but a table over positions is cheap.
  • "Can this prefix be built from allowed pieces" is the 1-D dynamic programming (DP) pattern that also appears in Decode Ways and Coin Change.

Start with brute force

Try each word as the first piece. If the string starts with it, recurse on the rest. Succeed when nothing is left.

def word_break_brute(s, words):
    if not s:
        return True
    for w in words:
        if s.startswith(w) and word_break_brute(s[len(w):], words):
            return True
    return False

Failures are not remembered, so the same suffix is explored many times. For "a" * 28 + "b" with the words a, aa, aaa it already takes several seconds, and the real limit is 300 letters. Time is exponential; space is O(n) for the recursion and slices.

From brute force to the idea

  1. Find the waste. Different ways of cutting the front often leave the same suffix, and the brute force re-tests it each time.
  2. Define a table. ok[i] is True if the first i letters can be split into dictionary words. ok[0] is True: the empty start needs no words.
  3. Test each position. For position i and each word w, the word would occupy s[j:i] where j = i - len(w). If j >= 0, ok[j] is True and s[j:i] == w, then ok[i] is True; stop checking words for this i.
  4. Answer. ok[len(s)].

This is the key idea: a prefix can be split if some word ends at its last letter and the part before that word can be split.

The key idea

ok[i] is True if some word w ends at position i and ok[i − len(w)] is True. This loop tries all W words at each of the n positions, comparing up to L letters each time: O(n · W · L). (The other common version tries every split point j < i and looks s[j:i] up in a set: O(n²) substring checks, each costing up to O(L) once pieces longer than the longest word L are skipped, so O(n² · L) at most.)

Python solution

def word_break(s, words):
    ok = [True] + [False] * len(s)  # s[:i]?
    for i in range(1, len(s) + 1):
        for w in words:
            j = i - len(w)  # w = s[j:i]?
            if j >= 0 and ok[j] and s[j:i] == w:
                ok[i] = True
                break
    return ok[len(s)]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceExponential: every position can branch into many words, suffixes are re-solvedO(n): recursion depth and slices
Table (shown code)O(n × W × L): n positions, W words, each comparison up to L letters (about 300 × 1,000 × 20 = 6 × 10^6)O(n): the ok list

Edge cases

  • Empty string: returns True (ok[0]), although the problem gives at least one letter.
  • Empty dictionary ("a", []): returns False.
  • Word reuse ("applepenapple", ["apple", "pen"]): returns True.
  • Almost works ("catsandog", ["cats", "dog", "sand", "and", "cat"]): returns False.
  • Overlapping words ("abcd", ["a", "abc", "b", "cd"]): returns True via a, b, cd, although abc also matches at the front and leaves d.
  • Word longer than the string: j is negative, so the j >= 0 guard skips it.
  • Dictionary words must be non-empty: an empty word would make j = i and compare against a position not yet decided. The problem guarantees length at least 1.

Common mistakes

  • Starting with ok[0] = False, so every answer is False.
  • Matching the longest word first and never going back. For "abcd" above that fails.
  • Slicing without the j >= 0 check, since a negative j slices from the end.
  • Comparing the slice before checking ok[j]. Both tests are needed, but checking the flag first skips most slice comparisons.
Your turn: count the splittings

Return the number of ways to split the string into dictionary words (words are distinct, order matters). For "aaaa" with ["a", "aa"] the answer is 5. Describe your approach, then write it if you like.

Compare with our answer

Same table, but each cell stores a count, and every matching word adds the count of the position before it.

def count_splits(s, words):
    ways = [1] + [0] * len(s)
    for i in range(1, len(s) + 1):
        for w in words:
            j = i - len(w)
            if j >= 0 and s[j:i] == w:
                ways[i] += ways[j]
    return ways[len(s)]

count_splits("aaaa", ["a", "aa"]) is 5, count_splits("aaaaaaa", ["aaaa", "aaa"]) is 2 and count_splits("a", ["b"]) is 0. Time O(n × W × L), space O(n).

A strong answer mentions: ways[0] = 1, adding ways[j] for every match instead of stopping at the first, that the break of the yes/no version has to go, and that distinct words mean no split is counted twice.

Check what stuck

1. You must test whether a 300-letter string can be built by joining words from a dictionary, reusing words freely. Which approach fits best?

2. What dominates the running time of the shown code?

3. A learner replaces the table with a greedy loop that always removes the longest dictionary word that matches the front. Which input does it get wrong?

Score 60% or more and the lesson is marked complete.