Word Break
Medium1-D dynamic programming
Given a string s and a list of words wordDict, return true if s can be cut into pieces that are each a word from the list, and false otherwise.
A word can be used any number of times.
Examples
Input: s = "sunflower", wordDict = ["sun", "flower"] Output: true
sun + flower.
Input: s = "carpets", wordDict = ["car", "pet", "carp"] Output: false
car + pet leaves s, and carp leaves ets. Neither is a word.
Constraints
1 ≤ s.length ≤ 3001 ≤ wordDict.length ≤ 10001 ≤ wordDict[i].length ≤ 20sand the words hold lowercase English letters only, and the words are all different.
Stuck?
Hint 1
Taking the first word that matches can lead you down a dead end. Ask instead, for every prefix of s: can this prefix be cut into words?
Hint 2
Prefix i can be cut if some shorter prefix j can be and s.slice(j, i) is a word. Put the words in a Set and fill a list of booleans from the empty prefix up.
The idea
Any way to cut the first i letters ends with some word, and the letters before that word must be cuttable too. So work out, for every prefix from the empty one up, whether it can be cut. Each answer uses only the answers for shorter prefixes, which are already known.
Time O(n³) for n letters, slicing each of n² cutsExtra space O(n + total length of the words)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
A Set answers whether a piece is a word in constant time, where searching the list would compare it with every word.
function wordBreak(s, wordDict) { const words = new Set(wordDict); const canCut = new Array(s.length + 1).fill(false); canCut[0] = true; for (let i = 1; i <= s.length; i++) { for (let j = 0; j < i; j++) { if (canCut[j] && words.has(s.slice(j, i))) { canCut[i] = true; break; } } } return canCut[s.length];}The trap
Taking the first word in the list that matches at the current position, then moving past it, finds a cut whenever the words never compete. When two words both match at a position, the one it takes can lead to a dead end while the other would have worked, and it never goes back to try it. Strings like that get false even though a cut exists.
function wordBreak(s, wordDict) { let i = 0; while (i < s.length) { const word = wordDict.find((w) => s.startsWith(w, i)); // the first match, never reconsidered if (!word) return false; i += word.length; } return true;}