MediumDynamic ProgrammingHash TableTrieUpdated Sep 2026

139. Word Break

Asked at Google, Meta, Amazon, Microsoft and 5 more

Difficulty

Medium

Time

O(n^2 * k)

Space

O(n)

Pattern

Dynamic Programming

Companies

9

Problem

You are given a string s and a list of words wordDict. Decide whether s can be split into a sequence of one or more words, where every piece is a word from wordDict and the pieces are joined back-to-back with no characters left over.

You may use the same dictionary word as many times as you like. The pieces must follow each other in order and cover the whole string — you cannot skip characters or rearrange them.

Return true if such a split exists, otherwise return false. The empty string is not a valid input here, since s has at least one character.

Can we cover the whole string?

sleetcodeleetcode01234567Two dictionary words placed side by side cover every character of s.scatsandcatsandog012345678Here the words stop at index 6, and the leftover "og" is not a word, so thissplit fails.
We must cut "leetcode" into dictionary words with no gaps and no leftover characters.

Constraints

  • ●1 <= s.length <= 300
  • ●1 <= wordDict.length <= 1000
  • ●1 <= wordDict[i].length <= 20
  • ●s and wordDict[i] consist of only lowercase English letters
  • ●All the strings of wordDict are unique

Examples

Example 1
Inputs = "leetcode", wordDict = ["leet","code"]
Outputtrue
WhyCut the string after 4 characters: "leet" is in the dictionary, and the rest "code" is also in the dictionary. Both pieces together cover the whole string, so the answer is true.
Example 2
Inputs = "applepenapple", wordDict = ["apple","pen"]
Outputtrue
WhySplit it as "apple" + "pen" + "apple". The word "apple" is used twice, which is allowed because dictionary words can be reused.
Example 3
Inputs = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Outputfalse
WhyYou can start with "cats" and then "and", but the leftover "og" is not a word. Other starts also leave a piece that is not in the dictionary, so no full split exists.

Asked At

9 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
NetflixMediumView all Netflix questions →
UberMediumView all Uber questions →
AtlassianMediumView all Atlassian questions →
SalesforceMediumView all Salesforce questions →

How to Think About It

1

dp[i] = true if s[0:i] can be segmented into dictionary words. Base case: dp[0] = true (empty string is always segmentable).

2

For each position i, try every possible last word: if dp[j] is true (s[0:j] is segmentable) AND s[j:i] is in the dictionary, then dp[i] = true.

3

Why it works: you're building solutions from left to right. If you can reach position j and there's a word from j to i, you can reach i.

4

Optimization: limit j to i - maxWordLength. No point checking positions further back than the longest dictionary word.

5

Trie optimization: instead of checking s[j:i] in a hash set, traverse a trie as you scan s from j to i. Stops early on mismatch.

6

Edge cases: empty string (true), single character in dict (check if it matches), overlapping words.

Optimal Approach

Step 1: Create dp array of size len(s)+1, all false. dp[0] = true.
Step 2: Convert wordDict to a set for O(1) lookup. Find max word length.
Step 3: For i from 1 to len(s):
For j from 0 to i:
If dp[j] and s[j:i] in word_set:
dp[i] = true
break
Step 4: Return dp[len(s)].

Time: O(n² × k) where k is max word length. Space: O(n).

DP over reachable positions

dp012345678TFFFFFFFFStart: only dp[0] is true, because the empty prefix needs no words.sleetleetcode01234567jiAt i = 4 we find j = 0 with dp[0] true and s[0:4] = "leet" in theset, so dp[4] becomes true.dp012345678TFFFTFFFTLater at i = 8, j = 4 works because dp[4] is true and s[4:8] ="code" is a word, so dp[8] is true.dp[i] = true if some j < i hasdp[j] == true and s[j:i] in wordDict
dp[i] is true when the first i characters can be split into dictionary words. We grow it left to right.
ComplexityTime O(n^2 * k)Space O(n)n is the length of s and k is the longest word length: for each end position we try each start position and compare a slice of up to k characters against the set.

What Trips People Up in Real Interviews

1

Confusing "word break" with "word search." This problem is about segmenting a string, not searching a grid.

2

Not using a set for dictionary lookups. Checking if a substring is in the dictionary is O(k) with a list but O(1) with a set.

3

Forgetting that dp[0] = true. The empty string is always segmentable.

4

Not optimizing the inner loop. No need to check j values further back than the longest dictionary word.

5

Not breaking out of the inner loop early. Once dp[i] is set to true for any j, you've found a valid segmentation — no need to check other split points. Breaking early avoids unnecessary work.

Solution Code

O(n^2 * k) time
def wordBreak(s, wordDict):
    word_set = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[len(s)]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Word Break 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.

How do you solve Word Break?

The optimal approach runs in O(n^2 * k) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Word Break?

Word Break is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Salesforce. It is a medium difficulty problem.

What are common mistakes on Word Break?
  • Confusing "word break" with "word search." This problem is about segmenting a string, not searching a grid.
  • Not using a set for dictionary lookups. Checking if a substring is in the dictionary is `O(k)` with a list but `O(1)` with a set.
  • Forgetting that `dp[0]` = `true`. The empty string is always segmentable.
  • Not optimizing the inner loop. No need to check j values further back than the longest dictionary word.
  • Not breaking out of the inner loop early. Once `dp[i]` is set to `true` for any j, you've found a valid segmentation — no need to check other split points. Breaking early avoids unnecessary work.