Every valid last word is its own branch
A prefix's count adds up every way it could end, one dictionary word at a time. About 12 minutes.
Group every split by its last word
A message arrived with the spaces missing: "catsanddog". Using a dictionary, how many ways can you put the spaces back?
Every way of splitting the text so far ends with some word. So for each position, look at every dictionary word that could end exactly there. For each one, count the ways to split everything before it. Different last words are different splits, so add them all up.
Two last words, both real
Start with 1 way to split nothing. "cat" and "cats" both fit at the start, so the text up to letter 3 and up to letter 4 each have 1 way.
At letter 7 two different last words fit: "sand" after "cat", and "and" after "cats". Both are real splits, so they add: 2. Then "dog" finishes both: 2 ways in total.
ways = [1] + [0] * len(s)
There's 1 way to split nothing. Under each letter is the number of ways to split the text up to there.
The text is "abab" and the dictionary is "a" and "ab". Which words could be the last piece of a split?
The text ends with the letters a, b.
- AOnly "ab"
- BBoth "a" and "ab"
- CNeither
Show the answer
Only "ab". The last two letters spell "ab". "a" would need the text to end in a.
Ways to break a word
Given a string s and a list of dictionary words, return how many different ways s can be split into a sequence of dictionary words (a word may be reused any number of times across different splits, and within one split).
s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"] → 2
0 ≤ s.length ≤ 1,000 · 0 ≤ wordDict.length ≤ 1,000 · lowercase English letters · return a long