How Many Segmentations
Count the DISTINCT ways to split the string into a sequence of dictionary words. Words may be reused, and every character must be covered. Two splits differ if they cut in different places.
Print the count modulo 1000000007.
aaaa, words a aa -> 5
abcd, words a b c d ab cd abc bcd -> 6
a, words b -> 0
The five splits of aaaa are a|a|a|a, a|a|aa, a|aa|a, aa|a|a and aa|aa.
## One operator changed
Problem 513 asks WHETHER a segmentation exists, with
ok[i] = OR over j of ( ok[j] and s[j..i-1] is a word )
This asks HOW MANY, with
ways[i] = SUM over j of ( ways[j] if s[j..i-1] is a word )
OR becomes addition and true becomes 1. Same loops, same bound, same dictionary.
That substitution is the single most reusable idea in DP: reachability, counting and optimisation share a recurrence and differ only in the operator. Recognising it means the second and third problems cost nothing once the first is written.
## Why no split is counted twice
Every segmentation has exactly one LAST word. Grouping the segmentations of the first i
characters by where that last word starts partitions them, so summing over j counts each
one once.
That is the same argument as counting by right endpoint in problem 475, and it is the argument that makes a sum a correct count rather than an overcount.
## The base case
ways[0] = 1, the empty segmentation. Not 0.
Setting it to 0 makes every entry 0, and the answer comes back 0 for every input, which at
least fails loudly. The subtler error is setting it to 1 but reading ways[n] when n is
0, which cannot happen here since the string is non-empty.
## Boundaries
abcd with a b c d ab cd abc bcd answers 6, and the overlapping words are the point: a
solution that stops at the first matching word per position answers 1.
aaaaaaa with aaa aaaa answers 2, from aaa|aaaa and aaaa|aaa. Same string as
problem 513's third sample, where the answer was just yes.
catsanddog with cat cats and sand dog answers 2, from cats|and|dog and
cat|sand|dog.
The count grows exponentially in n, which is why the modulus is in the statement.
## Cost
Time O(n * maxWordLength) substring tests. Space O(n) plus the dictionary.