Word Break (LeetCode 139) — DSA Visualizer

Problem

Given a string s and a dictionary of strings wordDict, return true if s can be split into a sequence of one or more dictionary words. The same word may be reused any number of times.

Example 1

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

Output: true ("leet code")

Example 2

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

Output: true ("apple pen apple" — words can be reused)

Example 3

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

Output: false

Constraints: 1 ≤ s.length ≤ 300 | 1 ≤ wordDict.length ≤ 1000 | lowercase English letters

📖 String & dictionary

⬆ dp[i] sits on the cut after the first i letters · ✅ buildable · ❌ not buildable

dictionary lookups: 0cuts skipped (dp[j] = ❌): 0

Variables

i (prefix length)

—

j (cut)

—

s[j..i)

—

dp[i]

—

💡 Step Logic

Press ▶ Play or Next to begin.

Ready

0 / 0

Pick an example and press Play.

Algorithm

Put the words in a HashSet; set dp[0] = true (empty prefix)

For each prefix length i = 1..n, try every earlier cut j

If dp[j] is ✅ and s[j..i) is a word → dp[i] = true, stop trying cuts

Return dp[n]

Time

O(n² · m)

Space

O(n)

🧠 Why DP, not greedy?

Greedy "always take the longest word" fails: for "abcd" with ["a","abc","b","cd"], grabbing "abc" leaves "d", which is no word, yet "a | b | cd" works. DP remembers every reachable cut, so no choice is ever lost. Speed-up: only try cuts j ≥ i − longestWord, since a longer piece can't be a word. (m = cost of building each substring.)

⚠️ Edge cases

Reusing words is allowed ("apple pen apple"). Almost-fits strings like "catsandog" fail only at the very end. That's why you must check dp[n], not just "most letters covered". A single-word string is true if that word is in the dictionary.