Skip to main content

21. Word Break

mediumAsked at Redis

Decide whether a string can be segmented into space-separated dictionary words; Redis uses it as a DP/memoization probe that overlaps with how the engine matches CONFIG GET glob patterns.

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

Constraints

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20

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. Recursive try every split

Try each prefix; recurse on suffix without memoization.

Time
O(2^n)
Space
O(n)
function tryBreak(s) {
  if (s === '') return true;
  for (const w of wordDict)
    if (s.startsWith(w) && tryBreak(s.slice(w.length))) return true;
  return false;
}

Tradeoff:

2. Bottom-up DP

dp[i] is true if s[0..i] is segmentable. Walk i = 1..n and check every j < i where dp[j] && wordSet.has(s[j..i]). Mirrors how Redis caches sub-results to avoid recomputing in nested LUA pcall stacks.

Time
O(n^2 * L)
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:

Redis-specific tips

Redis interviewers like the DP framing and reward you for mentioning how you'd back wordDict with a Redis SET membership lookup for distributed dictionary scenarios.

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

Practice these live with InterviewChamp.AI →