Skip to main content

29. Word Break

mediumAsked at Expedia

Determine whether a string can be segmented into dictionary words — Expedia applies this DP to validate that a raw destination-name string can be cleanly decomposed into known city and region tokens.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 in the dictionary may be reused multiple times.

Constraints

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters
  • All strings in wordDict are unique

Examples

Example 1

Input
s = "newyork", wordDict = ["new","york"]
Output
true

Example 2

Input
s = "miami", wordDict = ["mia","mi","ami"]
Output
true

Explanation: "mi" + "ami" = "miami".

Approaches

1. Recursive with memoization

At each position, try every word in the dictionary. If the prefix matches, recurse on the remaining suffix. Cache positions to avoid re-checking.

Time
O(n^2 * m) where m = avg word length
Space
O(n)
function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const memo = new Map();

  function dp(start) {
    if (start === s.length) return true;
    if (memo.has(start)) return memo.get(start);

    for (let end = start + 1; end <= s.length; end++) {
      if (words.has(s.slice(start, end)) && dp(end)) {
        memo.set(start, true);
        return true;
      }
    }
    memo.set(start, false);
    return false;
  }

  return dp(0);
}

Tradeoff:

2. Bottom-up DP

dp[i] = true if s[0..i) is breakable. For each i, check all j < i: if dp[j] is true and s[j..i) is a word, set dp[i] = true.

Time
O(n^2)
Space
O(n)
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];
}

Tradeoff:

Expedia-specific tips

Expedia's destination-data team has a version of this problem for normalizing user-typed location strings. They want you to identify the DP structure quickly: dp[i] asks 'can I build a valid prefix of length i?' and transitions from any valid shorter prefix. Mention that the Set lookup for s.slice(j,i) is O(word_length) and that a Trie could replace the set for faster prefix validation at scale.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Word Break and other Expedia interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →