Skip to main content

22. Word Break

mediumAsked at Wise

Decide if a string segments into dictionary words — Wise uses it as a stand-in for whether a multi-currency payment can be decomposed into legal corridor hops.

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

Problem

Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused.

Constraints

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= each word length <= 20

Examples

Example 1

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

Example 2

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

Approaches

1. Naive recursion

At each index try every prefix that matches a word and recurse on the suffix.

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

Tradeoff:

2. Bottom-up DP

dp[i] = true if s[0..i) is segmentable; for each i scan j<i and check dp[j] && s.slice(j,i) in dict. Linear table, O(n^2) scan.

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:

Wise-specific tips

Wise grades the DP framing — their corridor-decomposition engine uses the same dp[i] reachability shape, and they want to see you reach for it instead of memoized recursion.

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

Practice these live with InterviewChamp.AI →