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.
s = "leetcode", wordDict = ["leet","code"]true ("leet code")s = "applepenapple", wordDict = ["apple","pen"]true ("apple pen apple" — words can be reused)s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]falsedp[i] sits on the cut after the first i letters · ✅ buildable · ❌ not buildabledp[0] = true (empty prefix)i = 1..n, try every earlier cut jdp[j] is ✅ and s[j..i) is a word → dp[i] = true, stop trying cutsdp[n]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.)
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.
Trying every split recursively repeats the same suffix checks many times. Remember which prefixes can be built.
Let dp of i be true when the first i characters can be split into words. The empty prefix is always fine, so dp of 0 is true. For each end position i, look for a split point j where dp of j is true and the part from j to i is a dictionary word. If such a j exists, dp of i is true. The answer is dp of n.
Dp over prefixes, with a split point j. A true dp of j plus a dictionary word extends the prefix.
Run the animation above on your own input, or watch the 1:50 video explanation of Word Break with a dry run and Java code.