Skip to main content

21. Word Break

mediumAsked at Coursera

Determine if a string can be segmented into dictionary words, a DP problem Coursera uses to assess text-processing skills relevant to content tagging and search.

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 in the dictionary 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 = "applepenapple", wordDict = ["apple","pen"]
Output
true

Approaches

1. Recursive with memoization

Recursively try each prefix of the remaining string; memoize results by start index.

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

Tradeoff:

2. Bottom-up DP

dp[i] = can s[0..i) be segmented. For each i check all j<i: if dp[j] && s[j..i) is in dict then dp[i]=true. Final answer is dp[n].

Time
O(n^3)
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:

Coursera-specific tips

Coursera interviews emphasize algorithms for educational platforms, content recommendation systems, and scalable delivery pipelines. Medium-difficulty graph and DP problems are typical.

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

Practice these live with InterviewChamp.AI →