Word Break

Approach Summary

dp[i] = true if s[0..i) can be segmented. For each i, check all j < i where dp[j] is true and s[j..i) is a word.

Full Solution & Approach

Define dp[i] as whether the prefix s[0..i) can be segmented into dictionary words, with dp[0] = true (the empty prefix). For each end index i, scan all split points j < i: if dp[j] is true and s[j..i) is a word in the set, then dp[i] is true. Storing the dictionary in a set makes the substring lookup O(1) for each candidate, giving O(n² · m) worst case where m is the substring length in the check. The key correctness point is that dp[j] already encapsulates the possibility of segmenting everything before j, so a single true transition proves segmentability. Word Break II (returning the actual sentences) extends this with backtracking over the same dp table. The pattern — prefix DP over a string with a dictionary — also underlies palindrome-partitioning and regex-match problems.

Each of n end positions considers up to n split points with O(m) substring checks — O(n² · m) worst case. A boolean array of size n + 1 — O(n) space.

Solution Code

Solution

def word_break(s: str, word_dict: list[str]) -> bool:
    words = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

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 i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && words.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

bool wordBreak(const string& s, const vector<string>& wordDict) {
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (int i = 1; i <= (int)s.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && words.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

Edge Cases to Watch

Empty string — dp[0] = true per convention
A word that is a prefix of another — handled because every split point is tried
Dictionary words longer than s — never match
Characters in s not forming any word — dp stays false

How to Recognize This Pattern

Can string be segmented using dictionary?

Complexity Analysis

Time Complexity

O(n² × m)

Space Complexity

O(n)