Word Break

Problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Examples

The brute-force approach

Recursively try every possible split. At each position, try taking every word from the dictionary that matches a prefix of the remaining string.

def solve(start):
    if start == len(s): return True
    for word in wordDict:
        end = start + len(word)
        if s[start:end] == word and solve(end):
            return True
    return False
return solve(0)

O(2^n) without memoization — many subproblems are recomputed.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

If you know which prefixes of s can be segmented (dp[j] = true), how do you determine whether s[0..i-1] can also be segmented?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.