DSA Word Break

The problem

Word Break asks whether a string can split fully into words from a given word set. A split covers the whole string. No letters are left over, and no letters are skipped.

The answer is True or False. The article also recovers one full split when one exists. A word from the set may be used more than once.

cases = [
    ("leetcode", ["leet", "code"], True),
    ("applepenapple", ["apple", "pen"], True),
    ("catsandog", ["cats", "dog", "sand", "and", "cat"], False),
    ("aaaaaaa", ["aaaa", "aaa"], True),
]
for s, words, expected in cases:
    print("string", s, "words", words, "can break:", expected)

Read the third row with care. The string catsandog starts well with its set words. Its last letters still block a full split.

Intuition: take the longest word that fits

The first idea scans from the start. It takes a set word that matches at the current position. Taking the longest match feels safest, because it covers the most letters.

That greedy choice can strand the tail. The block below shows the trap on a tiny string.

s = "aaaa"
words = {"aa", "aaa"}
pos = 0
taken = []
while pos < len(s):
    matches = [w for w in words if s.startswith(w, pos)]
    if not matches:
        break
    word = max(matches, key=len)
    taken.append(word)
    pos += len(word)
print("greedy took:", taken)
print("letters covered:", pos, "of", len(s))
print("the split aa + aa works:", "aa" in words and "aa" in words)

The greedy run took aaa and stalled at one letter. The split aa plus aa covers the whole string. A full search must be ready to back away from a long match.

Brute force: try every cut from every position

The brute force tries each set word at the current position. It then solves the rest of the string the same way. No position result is stored, so the same tail is solved again and again.

calls = 0

def can_break(s, words, start):
    global calls
    calls += 1
    if start == len(s):
        return True
    for end in range(start + 1, len(s) + 1):
        if s[start:end] in words and can_break(s, words, end):
            return True
    return False

words = {"a", "aa"}
for n in [6, 8, 10]:
    calls = 0
    result = can_break("a" * n + "b", words, 0)
    print("length", n + 1, "can break:", result, "calls:", calls)

The trailing b makes every split fail. The brute force only learns that after trying the cuts. Its call count climbs fast as the string grows.

The optimal solution: spread reachable positions

The state is reachable(i), which is true when the first i characters split fully into set words. A position spreads forward through every set word that starts there.

The start position 0 is reachable, because the empty prefix needs no words. The answer is the value at the final position. A parent records one word start per reached position, so one split can be rebuilt.

def word_break(s, words):
    parent = [-1] * (len(s) + 1)
    parent[0] = 0
    for end in range(1, len(s) + 1):
        for start in range(end):
            if parent[start] != -1 and s[start:end] in words:
                parent[end] = start
                break
    if len(s) > 0 and parent[len(s)] == -1:
        return False, []
    pieces = []
    end = len(s)
    while end > 0:
        start = parent[end]
        pieces.append(s[start:end])
        end = start
    pieces.reverse()
    return True, pieces

cases = [
    ("leetcode", {"leet", "code"}, True),
    ("applepenapple", {"apple", "pen"}, True),
    ("catsandog", {"cats", "dog", "sand", "and", "cat"}, False),
    ("aaaaaaa", {"aaaa", "aaa"}, True),
]
for s, words, expected in cases:
    answer, pieces = word_break(s, words)
    print("string:", s, "->", answer, "split:", pieces, "match:", answer == expected)

All four cases from the start of the article pass. The greedy trap string also splits here, as a later edge case shows. Reachable positions never commit to one greedy choice.

Walkthrough: leetcode, position by position

The walk fills the reachable table from left to right. Each row names the end position and the word that reached it, when one did.

s = "leetcode"
words = {"leet", "code"}
reachable = [False] * (len(s) + 1)
reachable[0] = True
print("position 0 reachable: True (start)")
for end in range(1, len(s) + 1):
    found = None
    for start in range(end):
        if reachable[start] and s[start:end] in words:
            found = s[start:end]
            reachable[end] = True
            break
    print("position", end, "reachable:", reachable[end], "word:", found)
print("positions:", [i for i in range(len(s) + 1) if reachable[i]])
print("verdict:", reachable[-1])

Only positions 0, 4, and 8 are reachable. Position 4 comes from leet. Position 8 comes from code, and it is the final position, so the verdict is True.

Complexity

The table checks pairs of positions, so its time is O(n^2) substring checks for a string of length n. The table and the parent list each hold one entry per position, so the space is O(n).

calls = 0

def can_break(s, words, start):
    global calls
    calls += 1
    if start == len(s):
        return True
    for end in range(start + 1, len(s) + 1):
        if s[start:end] in words and can_break(s, words, end):
            return True
    return False

words = {"a", "aa"}
for n in [6, 8, 10]:
    calls = 0
    can_break("a" * n + "b", words, 0)
    checks = (n + 1) * (n + 2) // 2
    print("length", n + 1, "- brute calls:", calls, " table pair checks:", checks)

The brute calls grow faster than the pair checks. The table pays each pair of positions once. The brute force pays for the same tail many times.

Edge cases and pitfalls

The empty string splits with no words at all. Its verdict is True. A middle position can stay unreachable while the final verdict is still True, as the walkthrough showed.

def word_break(s, words):
    reachable = [False] * (len(s) + 1)
    reachable[0] = True
    for end in range(1, len(s) + 1):
        for start in range(end):
            if reachable[start] and s[start:end] in words:
                reachable[end] = True
    return reachable[-1]

print("empty string:", word_break("", {"a"}))
print("greedy trap aaaa:", word_break("aaaa", {"aa", "aaa"}))
print("word reused:", word_break("aa", {"a"}))
print("tail blocked:", word_break("catsandog", {"cats", "dog", "sand", "and", "cat"}))
print("no word fits at all:", word_break("abc", {"ab"}))
print("unused words ignored:", word_break("ab", {"ab", "zz"}))

Reuse is allowed in this problem. The word a covers aa by appearing twice. Reading only the final position gives the verdict, never the middle rows.