1D DP

Word Break

Can the string be segmented into dictionary words? dp[i] = true if s[0..i] can be segmented. For each position i, check every word: if dp[i − len(word)] is true AND s[i−len..i] matches the word, then dp[i] = true.

O(n² * m)

O(n)

How It Works

Word Break decides whether a string can be split into dictionary words. Let dp[i] be true if the prefix s[0..i) is segmentable, with dp[0] = true for the empty prefix. For each position i, check every dictionary word (or every earlier split point j): if dp[j] is true and s[j..i) is in the dictionary, then dp[i] is true. Each prefix is decided once, so the exponential set of segmentations collapses into n boolean states.

With a hash set for O(1) word lookups, the double loop runs in O(n^2) substring checks (times substring length for hashing), far better than the O(2^n) backtracking worst case on adversarial inputs like long runs of 'a' with no full match. Bounding the inner loop by the longest word length is a common speedup.

Step-by-Step Visualization

Can 'leetcode' be split into ['leet','code']?

dp[0]true (empty string)

1/3

Code

Java

static boolean wordBreak(String s, List<String> wordDict) {
  Set<String> set = new HashSet<>(wordDict);
  boolean[] dp = new boolean[s.length() + 1];
  dp[0] = true;

  for (int i = 1; i <= s.length(); i++) {
    for (int j = 0; j < i; j++) {
      if (dp[j] && set.contains(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length()];
}
// wordBreak("leetcode", Arrays.asList("leet","code")) → true

Tips & Gotchas

1dp[i] = true if s[0..i] can be segmented into dictionary words

2For each position i, check all possible last words

3Use a Set for O(1) dictionary lookup

Practice Problems

1Word Break
2Word Break II
3Concatenated Words
4Extra Characters in a String

About the 1D DP Pattern

The state is a single variable (usually an index). Each dp[i] depends on a few previous values like dp[i−1] or dp[i−2]. Often you can optimize space by keeping only the last 2-3 values instead of the whole array.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

Why does plain backtracking time out on Word Break?

Backtracking re-explores the same suffixes repeatedly; a string like 'aaaa...b' with dictionary {'a','aa','aaa'} creates exponentially many failing paths. Memoizing whether each start index is segmentable makes every suffix a solved-once subproblem.

How is Word Break II different, and why is it harder?

Word Break II asks for all valid sentences, not just a yes/no answer, so the output itself can be exponential in size. You still memoize per start index, but you cache lists of partial sentences, and worst-case time is dictated by the number of answers.

Should I iterate over split points or over dictionary words?

If the dictionary is huge but its longest word is short, iterate positions and only look back up to the max word length. If words are few, looping over the dictionary at each position can be faster. Both are correct; pick based on which dimension is smaller.