Question

Describe recursive algorithms for the following variants of the text segmentation problem. Assume that you have a subroutine IsWord that takes an array of characters as input and returns True if and only if that string is a “word”. (a) Given an array A[1 .. n] of characters, compute the number of partitions of A into words. For example, given the string ARTISTOIL, your algorithm should return 2, for the partitions ARTIST·OIL and ART·IS·TOIL.

Do this by appropriately modifying the following pseudo-code :

Splittable(i):

.........if i > n

...............return True

.......for j ← i to n

.............if IsWord(i, j)

....................if Splittable(j + 1)

.........................return True

......return False

Answer 1