Word Break

Problem (restated)

Can string s be segmented into a space-separated sequence of one or more dictionary words? Words may reuse.

Intuition

dp[i] = true if s[:i] can be segmented. Transition: some j < i with dp[j] and s[j:i] in dict.

Approaches

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

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

Template connection

1D DP on string prefixes / unbounded word reuse.

Reflection

• dp[i] is true when s[0:i] can be split into dictionary words. That holds when some s[j:i] is a word and dp[j] is true.
• dp[0], the empty prefix, is true. An empty dictionary word would close a loop; this problem has none.
• If the end is never reached, the answer is false. One letter that is in the dictionary is true.