Text Segmentation

Optimizing the text segmentation problem

For our next dynamic programming algorithm, let’s consider the text segmentation problem from the previous chapter. We’re given a string $A[1 .. n]$ and a subroutine $IsWord$ that determines whether a given string is a word, and we want to know whether $A$ can be partitioned into a sequence of words.

We solved this problem by defining a function $Splittable(i)$ that returns $True$ if, and only if, the $suffix\space A[i .. n]$ can be partitioned into a sequence of words. We need to compute $Splittable(1)$. This function satisfies the recurrence

$$Splittable(i)=\{\begin{array}{ll}& \text{ True }ifi>n\\ & \end{array}$$ ...