Skip to main content

19. Word Break

mediumAsked at Squarespace

Decide whether a string can be segmented into a sequence of dictionary words; Squarespace uses it to test DP memoization on top of recursion.

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 dictionary word may be reused.

Constraints

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • wordDict has no duplicates

Examples

Example 1

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

Example 2

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

Approaches

1. Naive recursion

Try every prefix that's in the dictionary and recurse on the suffix. Exponential without memoization.

Time
O(2^n)
Space
O(n)
const set=new Set(wordDict);
const go=t=>{ if(t==='') return true;
  for(let i=1;i<=t.length;i++) if(set.has(t.slice(0,i))&&go(t.slice(i))) return true;
  return false; };
return go(s);

Tradeoff:

2. Bottom-up DP

Let dp[i] mean s[0..i) is segmentable. Build it left to right by checking every prior dp[j] where s[j..i) is in the dictionary.

Time
O(n^2)
Space
O(n)
function wordBreak(s, wordDict) {
  const set = 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] && set.has(s.slice(j, i))) { dp[i] = true; break; }
    }
  }
  return dp[s.length];
}

Tradeoff:

Squarespace-specific tips

Squarespace likes a note that this same prefix-matching DP underlies their URL-pattern resolver, which splits an incoming path into known route segments at publish time.

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 Squarespace interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →