#139 - Word Break

MediumDP - 1D

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. The same word may be reused multiple times.

Input	Output
s = "leetcode", wordDict = ["leet","code"]	true
s = "applepenapple", wordDict = ["apple","pen"]	true
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]	false

Solution Space

Try it

/**
 * Returns true if s can be segmented into words from the dictionary.
 *
 * dp[i] = true if s[0..i) can be segmented.
 * For each position i, check all words: if dp[i - word.length] is true
 * and s ends with that word at position i, then dp[i] = true.
 *
 * @param s        Input string
 * @param wordDict Dictionary of valid words
 * @returns        Whether s can be fully segmented
 */
export function wordBreak(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict);
  const n = s.length;
  const dp = new Array<boolean>(n + 1).fill(false);
  dp[0] = true; // empty string is segmentable

  for (let i = 1; i <= n; i++) {
    for (const word of words) {
      const len = word.length;
      if (len <= i && dp[i - len] && s.slice(i - len, i) === word) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[n];
}

Approach: bottom-up DP – `dp[i]` is true if `s[0..i)` is segmentable. For each position, try every dictionary word as the potential last segment.

Time: O(n · m · k) – n positions, m words, k average word length for `slice` comparison.

Space: O(n) – the DP array.

Alternative approaches:

Approach	Idea	Time	Space
Trie + DP	Build a trie from the dictionary; at each DP position, walk the trie forward to find all matching words	O(n · L) where L is max word length	O(n + total chars in dict)
BFS/DFS with memoization	Treat each valid split point as a graph node, BFS/DFS from index 0 to n	O(n · m · k)	O(n)

Why the basic DP approach is preferred: simple, iterative, and easy to reason about. The Trie approach is better when the dictionary is very large.

#216 Combination Sum III

#198 House Robber