Word Break Problem — DP over Substrings

State

dp[i] = can we break s[0..i-1] into dictionary words?

Transition

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] && dict.contains(s.substring(j, i))) {
      dp[i] = true; break;
    }
return dp[s.length()];

Complexity

O(N² × K) where K = substring lookup cost. Use HashSet for O(1) contains.

Return actual sentences

Similar DP but track predecessors. Backtrack to reconstruct all valid segmentations.