Given a string and a dictionary of words, decide whether the string can be split into a sequence of dictionary words. Words may be reused.
DSA Animator › DSA Revision › Dynamic Programming › Word Break
Remember: dp over prefixes, with a split point j. A true dp of j plus a dictionary word extends the prefix. The video solves Word Break (LeetCode 139, Medium) with the 1D DP over Prefixes pattern from the Dynamic Programming topic, and you can replay every step in the interactive Word Break animation.
Given a string and a dictionary of words, decide whether the string can be split into a sequence of dictionary words. Words may be reused.
For leetcode with the dictionary leet and code, the answer is true. The split is leet, then code.
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 of 0 is true. Positions 1 to 3 cannot be built, because l, le and lee are not words. At position 4, dp of 0 is true and leet is a word, so dp of 4 becomes true. Positions 5 to 7 stay false. At position 8, dp of 4 is true and code is a word, so dp of 8 becomes true. So the answer is true.
In code, put the dictionary into a hash set. Create a boolean array with dp of 0 set to true. For each i, loop j from 0 to i, and if dp of j is true and the substring is in the set, mark dp of i and break. Return dp of n, so it's O of n squared substring checks.
Remember: dp over prefixes, with a split point j. A true dp of j plus a dictionary word extends the prefix.