Word Break

Why it belongs on this sheet

This is a great bridge problem between strings and DP because the state is defined over prefixes.

Pattern

Prefix validity DP

Approach

Let dp[i] tell you whether the prefix ending at i can be segmented. For every ending position, try all earlier split points and check whether the suffix is in the dictionary.

Java solution

import java.util.HashSet;
import java.util.List;
import java.util.Set;

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

    for (int end = 1; end <= s.length(); end++) {
      for (int start = 0; start < end; start++) {
        if (dp[start] && words.contains(s.substring(start, end))) {
          dp[end] = true;
          break;
        }
      }
    }

    return dp[s.length()];
  }
}

Complexity

• Time: O(n^3) in Java with substring creation in the naive form
• Space: O(n + dictionary size)

Interview note

The state answer is simply: "can the prefix up to here be fully segmented?"