The space bar has stopped working on Katt's cellphone, so that now the words in his mail messages all run together with no spaces. Actually, the punctuation marks aren't working either. It's a real mess!
So Katt wants you to design an algorithm that, given a string X, determines e?ciently how many ways X can be broken up into a sequence of words. You may use Katt's word tester as a "black box" subroutine, so that given a pair i and j ≥ i, you can test in constant time whether xixi+1 · · · xj is a valid word.
Also analyze the running time of your algorithm.