Faangprep Logo
Log inStart free
Browse curriculum

Word Break

Decide whether the string s can be cut, end to end, into pieces that each appear in a given list of dictionary words, where any word may be used more than once.

Medium
11 min
Solve on LeetCode

Examples

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

The cut at 4 reaches "leet", and "code" finishes it.

Input:s = "applepenapple", wordDict = ["apple","pen"]
Output:true
Explain:

Dictionary words may be reused, so "apple" is used twice.

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

Both "cats" and "cat" start it, but neither leaves a remainder the dictionary can finish.

Problem Understanding

We need to check if the entire string can be built using dictionary words. Words can be reused.

Example: s = "leetcode", dict = ["leet", "code"]

  • "leet" + "code" -> Valid
  • Output: true

Algorithm Strategy

Let dp[i] be true when the first i characters can be cut into dictionary words.

Recurrence: dp[i] is true if there is some j < i where

  1. dp[j] is true — the first j characters already segment, and
  2. s[j...i) is in the dictionary.

Base case: dp[0] = true. The empty prefix needs no words, and it is what the first real word stands on.

One working j settles the question, so the inner loop stops at the first one it finds.

Interactive Visualization

Column i is the verdict on the first i characters. When a cut point is tested, its cell and the letters of the piece between it and i light together — so dp[j] and s[j:i] in words can be read straight off the picture.

Try Example 3: "cats" and "cat" both start it, and neither leaves a remainder the dictionary can finish.

Dry Run

s = "applepen", dict = ["apple", "pen"]

i Substr tested Valid split at j? dp[i] Result
0 "" - T (Base)
... ... ... ...
5 "apple" j=0 (dp[0]=T) & "apple" in dict T
... ... ... ...
8 "pen" (from 5) j=5 (dp[5]=T) & "pen" in dict T

Edge Cases & Common Mistakes

Common pitfalls:

  • Words may be reused. "applepenapple" needs "apple" twice, and nothing in the recurrence forbids it — dp never tracks which words were spent.

  • dp[0] = true is what starts it. Without it no first word can ever be accepted, because every cut of a prefix has to stand on an earlier true cell.

  • An early word is not a commitment. "catsandog" reaches "cats" and gets stuck, and reaching "cat" does not help either. Only a false at dp[n] settles it.

Solution

Every cut point tried, stopping at the first that works — the lines light up as the figure above steps.

Word Break Code
1var wordBreak = function(s, wordDict) {
2    const n = s.length;
3    const words = new Set(wordDict);
4    const dp = new Array(n + 1).fill(false);
5    dp[0] = true;
6    for (let i = 1; i <= n; i++) {
7        for (let j = 0; j < i; j++) {
8            if (dp[j] && words.has(s.slice(j, i))) {
9                dp[i] = true;
10                break;
11            }
12        }
13    }
14    return dp[n];
15};
Previous

Longest Increasing Subsequence

Next

Maximum Profit in Job Scheduling

The approach, step by step

  1. Index by prefix length

    Let dp[i] be true when the first i characters split into words, and set dp[0] = true.

  2. Try every cut point

    For each i, walk every earlier j and ask whether dp[j] is true and s[j..i) is in the dictionary.

  3. Stop at the first witness

    One working cut point settles dp[i], so break out and move on to the next prefix.

Frequently asked questions

What does dp[i] mean in Word Break?

dp[i] is true when the first i characters can be cut into dictionary words. dp[0] is true because the empty prefix needs no words at all, and that is what the first real word builds on.

Why is the inner loop allowed to break early?

The problem asks whether a segmentation exists, not how many there are. One working cut point is a complete proof for that prefix, so the loop stops at the first one — later cut points cannot change a true into anything else.

Why is this O(n² · k) and not O(n²)?

There are O(n²) pairs of i and j, and each one slices out a substring and hashes it to look it up. That slice costs O(k) for a piece of length k, so the substring work has to be counted. A trie over the dictionary removes it.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description