Word Break

Examples

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

"leetcode" splits into "leet" + "code".

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

"applepenapple" splits into "apple" + "pen" + "apple", reusing "apple".

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

No combination of the given words covers the whole string cleanly — "catsandog" always leaves a leftover chunk like "og" that isn't a word.

Constraints

• 1 <= s.length <= 300

• 1 <= wordDict.length <= 1000

• s and every word in wordDict consist of lowercase English letters

Approach

Ask the question one position at a time: starting from index i, can the rest of the string be broken into dictionary words? That's true exactly when some dictionary word matches the string starting right at i, and the remainder after that word can also be broken — which is the exact same question, just starting further along.

That gives a clean recursive definition, with the empty remainder (past the end of the string) as the trivially true base case. Plain recursion re-asks the same "can this suffix be broken?" question many times through different paths, so caching each answer — or building them up from the end of the string backward — avoids the repeated work.

Solutions

Brute Force — Plain Recursion

From each starting position, try every dictionary word that matches there, and recurse on whatever's left. Correct, but the same starting positions get re-explored repeatedly through different word choices.

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);

  function canBreak(start) {
    if (start === s.length) return true;

    for (const word of words) {
      if (s.startsWith(word, start) && canBreak(start + word.length)) {
        return true;
      }
    }
    return false;
  }

  return canBreak(0);
}

Time: O(2^n * m) — exponential branching, m = average word length for the startsWith checks · Space: O(n) — recursion depth

Optimal — Bottom-Up Tabulation

Work backward from the end of the string. dp[i] records whether the suffix starting at i can be broken into dictionary words, built from the already-solved dp values for positions after it.

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const n = s.length;

  // dp[i] = can the suffix s[i..n) be broken into dictionary words?
  const dp = new Array(n + 1).fill(false);
  dp[n] = true; // the empty suffix is trivially breakable

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

  return dp[0];
}

Time: O(n * w * m) — n positions, w dictionary words, m average word length for matching · Space: O(n + w) — the dp array plus the word set