Word Break

Signal

"Can this prefix be built from pieces in a dictionary" is a segmentation shape — whether position i is reachable depends on whether some earlier break point j was reachable and the piece between j and i is a valid word.

Approach

Let dp[i] mean "the first i characters can be fully segmented". dp[0] is true (the empty prefix trivially segments). For each i, check every earlier j: if dp[j] is true and s[j:i] is a dictionary word, then dp[i] is true. The answer is dp[len(s)].

Skeleton

words = set(word_dict)
dp = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
    for j in range(i):
        if dp[j] and s[j:i] in words:
            dp[i] = True
            break
return dp[len(s)]

Solution

def word_break(s: str, word_dict: list[str]) -> bool:
    words = set(word_dict)
    dp = [True] + [False] * len(s)

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break

    return dp[len(s)]

Complexity

O(n² ) time in the worst case — the double loop over break points, with O(1) average dictionary lookups via a set (each slice s[j:i] costs up to O(n), making it O(n³) in the strictest accounting, but the set lookup itself is O(1)). O(n) space for dp plus O(total dictionary length) for the word set.

Pitfalls

• Checking membership against a list instead of a set turns each lookup into O(dictionary size), silently making the whole thing much slower.
• This asks "can it be segmented at all", not "list all segmentations" — don't over-build a backtracking solution that enumerates every valid split unless the interviewer explicitly asks for Word Break II.
• Forgetting dp[0] = True means no prefix can ever start being marked reachable, and the function always returns False.