Please write a full answer and give a good explanation!

4. Describe efficient algorithms for the following variants of the text segmen- tation 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". Analyze your algorithms by bounding the number of calls to IsWORD. (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. (b) Given two arrays A[1..n] and B[1..n] of characters, decide whether A and B can be partitioned into words at the same indices. For example, the strings BOTHEARTHANDSATURNSPIN and PINSTARTRAPSANDRAGSLAP can be partitioned into words at the same indices as follows: BOT HEART HAND SAT URNS PIN PIN START RAPS AND.RAGS LAP (c) Given two arraysA[1..n] and B[1.. n] of characters, compute the number of different ways that A and B can be partitioned into words at the same indices. 4. Describe efficient algorithms for the following variants of the text segmen- tation 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". Analyze your algorithms by bounding the number of calls to IsWORD. (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. (b) Given two arrays A[1..n] and B[1..n] of characters, decide whether A and B can be partitioned into words at the same indices. For example, the strings BOTHEARTHANDSATURNSPIN and PINSTARTRAPSANDRAGSLAP can be partitioned into words at the same indices as follows: BOT HEART HAND SAT URNS PIN PIN START RAPS AND.RAGS LAP (c) Given two arraysA[1..n] and B[1.. n] of characters, compute the number of different ways that A and B can be partitioned into words at the same indices