loading

Word Break — Step-by-Step Visualization

mediumLeetCode #139ArrayHash TableDynamic ProgrammingStringMemoization

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. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Algorithm Pattern

1D Dynamic Programming (Bottom-Up)

Key Idea

We use a boolean array `dp` of size `len(s) + 1`. `dp[i]` is true if the prefix `s[0...i-1]` can be segmented into words from the dictionary. For each index `i`, we check all possible preceding indices `j`. If `dp[j]` is true AND the substring `s[j...i]` exists in the dictionary, then `dp[i]` is true.

Step-by-Step Approach

  1. Initialize `dp` array with `False`, size `n + 1`.
  2. Base case: `dp[0] = True` (empty string is always matchable).
  3. Outer loop: iterate `i` from 1 to `n` (ending position of substring).
  4. Inner loop: iterate `j` from 0 to `i-1` (starting position of substring).
  5. If `dp[j]` is True and `s[j:i]` is in `wordDict`, set `dp[i] = True` and break inner loop.
  6. Return `dp[n]`.

Common Gotchas

  • The order of loops should be such that we build up from smaller prefixes.
  • Using a Set for `wordDict` lookups is faster (O(1)).

Related Problems

← All problems