50. Word Break

Problem

A tokenizer-validation tool needs to sanity-check that a raw, space-stripped string reconstructed from a detokenization step can actually be re-split into a sequence of tokens drawn only from the known vocabulary. Given a string s and a list of vocabulary tokens word_dict, determine whether s can be segmented into one or more of those tokens, concatenated in order (tokens may repeat).

Source: src/50_word_break.py

def can_segment(s: str, word_dict: list[str]) -> bool: ...

>>> can_segment("tokenizer", ["token", "izer"])
True

>>> can_segment("tokenbroken", ["token", "izer"])
False

Step-by-Step Approach

1. Define dp[i] as "can s[:i] (the first i characters) be fully segmented using dictionary words." The answer to the whole problem is dp[n], where n = len(s).
2. Base case: dp[0] = True — the empty prefix is trivially segmentable (zero tokens needed).
3. For each end position i from 1 to n, try every dictionary word as a candidate for the LAST token ending at i.
4. For a candidate word of length len(word), the token would start at j = i - len(word). It's a valid choice exactly when j >= 0, dp[j] is already True (the prefix before the token is itself segmentable), and s[j:i] == word (the characters actually match).
5. The moment any candidate word satisfies all three conditions, set dp[i] = True and stop checking further words for this i — one valid last token is enough.
6. Return dp[n].

The key insight is that segmentability is compositional: s[:i] is segmentable if and only if there's SOME split point where everything before it is already known to be segmentable AND the remaining suffix up to i is itself a single dictionary word — which is exactly what makes this a 1D DP over string prefixes rather than needing to enumerate every possible full segmentation.

Reference solution

def can_segment(s: str, word_dict: list[str]) -> bool:
    # dp[i] = whether s[:i] can be fully segmented; for each end position,
    # try every dict word as the LAST token and check the remaining prefix.
    # O(n * len(word_dict) * max_word_len) time, O(n) space.
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty prefix is trivially segmentable
    for i in range(1, n + 1):
        for word in words:
            j = i - len(word)
            if j >= 0 and dp[j] and s[j:i] == word:
                dp[i] = True
                break  # one valid last-token choice is enough for this i
    return dp[n]

Key Functions & Tricks

• set(word_dict) — deduplicates the dictionary and gives fast membership semantics, though the loop here still checks each word explicitly to find its length and matching substring.
• dp[i - 1]-style prefix DP — building the answer for position i strictly from already-computed smaller positions.
• s[j:i] == word — the actual substring-equality check that confirms a candidate word truly occurs at that position.
• break on the first valid word — short-circuits the inner loop once dp[i] is known to be True, since further checks can't change the answer.
• dp = [False] * (n + 1) — the +1 sizing lets index 0 cleanly represent the empty prefix, avoiding off-by-one special casing.

How to Recognize This Pattern