Skip to main content
SeniorPath
Browse content
Menu / Close menu

March 24

Word Break

How to turn string segmentation into prefix dynamic programming instead of retrying the same cut over and over.

Dynamic Programming Intermediate 22 min TypeScript

#interviews#dynamic-programming#strings

Given a string s and an array wordDict, return true if s can be segmented into one or more dictionary words.

You may reuse words from the dictionary as many times as needed.

Example:

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

What to notice before coding

  • The problem does not ask you to list every segmentation. It only asks whether one exists.
  • The natural question becomes about prefixes, not the whole string all at once.
  • Fast dictionary lookup helps a lot.

Common mistakes

  • repeating the same suffix check many times in recursion
  • keeping the dictionary as an array and paying linear lookup every time

Step 1 - Understand what is being asked

The problem does not want all possible ways to split the string.

It wants a boolean answer:

  • does some valid segmentation exist?

That already suggests you may not need to carry every combination.

Step 2 - Write the recursive baseline

The natural baseline is:

  • try every possible cut
  • if the current prefix is in the dictionary, test the rest

It works.

But it repeats many suffixes.

Step 3 - Reframe it as a prefix question

Instead of asking "can the whole string be segmented?", ask:

  • can the first i characters be segmented?

That becomes a good DP definition:

  • dp[i] = true if s.slice(0, i) can be segmented

Step 4 - Find the transition

For dp[i] to be true, it is enough that some j < i satisfies:

  • dp[j] is already true
  • s.slice(j, i) is in the dictionary

If that happens, the prefix up to i also works.

The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.

Starter code

export function wordBreak(s: string, wordDict: string[]): boolean {
  // your solution here
  return false
}
solution.ts
Stuck? Hints available.

Haven't solved it yet?

Viewing the solution now may reduce learning. It's worth trying a bit more.

Open the reference solution

Without JavaScript, the reference solution is shown inline instead of in a dialog.

Solution

Final complexity

Time: O(n^2)

Space: O(n)

Solution 1 - Recursion trying every cut

Good baseline because it shows exactly where repeated work comes from.

export function wordBreak(s: string, wordDict: string[]): boolean {
  function dfs(start: number): boolean {
    if (start === s.length) {
      return true
    }

    for (let end = start + 1; end <= s.length; end += 1) {
      const candidate = s.slice(start, end)

      if (wordDict.includes(candidate) && dfs(end)) {
        return true
      }
    }

    return false
  }

  return dfs(0)
}

It works, but it re-explores many of the same suffixes.

A halfway improvement would be memoization: cache the answer for each start so the same suffix is not solved twice.

Solution 2 - Prefix dynamic programming with a hash set in O(n^2)

Now you store what you already know about each prefix.

export function wordBreak(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict)
  const dp = new Array(s.length + 1).fill(false)
  dp[0] = true

  for (let end = 1; end <= s.length; end += 1) {
    for (let start = 0; start < end; start += 1) {
      if (!dp[start]) {
        continue
      }

      if (words.has(s.slice(start, end))) {
        dp[end] = true
        break
      }
    }
  }

  return dp[s.length]
}

The central idea is turning “try all cuts” into “reuse what I already know about earlier prefixes.”

In JavaScript, Set is the practical way to get hash set-style lookup for dictionary words.

What to say in the interview

A strong short explanation would be:

The recursive baseline tries every cut and repeats the same suffix checks many times. The stronger version switches to prefix DP. dp[i] says whether the first i characters can be segmented. Then I test whether there exists some j with dp[j] = true and substring s.slice(j, i) in the dictionary.

That shows that you:

  • identified the repeated work
  • chose a clear state definition
  • connected the transition to a simple question

When this pattern shows up again

This pattern comes back when you need to:

  • validate string segmentation
  • do DP over prefixes
  • replace recursive trial-and-error with subproblem reuse
  • combine dynamic programming with strings

The point is not memorizing Word Break.

The point is learning to turn cuts into prefix state.
Next challenge Trapping Rain Water Previous challenge Longest Palindromic Substring

Related challenges

Climbing Stairs

Coin Change

Longest Substring Without Repeating Characters

Related articles

Thinking Before You Code in Interviews

Breaking Problems Down

Recognizing Problem Patterns