Top-Down Approach for Palindrome Partitioning Problem

This article explains the Palindrome Partitioning Problem and how to solve it using Top-Down Approach with Java Codes and References. It covers the pseudocode, recursion, and memoization techniques used to solve the problem. The program uses Dynamic Programming solution storing the correct answers to subproblems in two arrays namely pal[][] and count[][], and keeps reusing the values stored.

Top-down approach; pseudocode with java codes and references
Pseudocode and description of the problem using top-down approach ,recursion and memoization.
Given input as String strin;
// i is the beginning index passed as i=0 while j marks the end index j=n-1;
Using recurrence, search for the partions and then store them in an array while making Boolean array
true; Below is an optimal substructure of the program
//Base cases
If the length of string ==1
BestPal(strin,i,j)=1;
If the String is a palindrome then
Bestpal(strin,i,j)==1;
If both of them are false,then
Bespal(strin,i,j) is computed through recurrence implementing the following formula
Bestpal(strin,i,j)=Minimum{Bestpal(strin,i,k) + k + 1 + Bestpal(strin,i,k +1,j)}
Where the k changes ranging from (i) to j-1;
Note if a more optimized solution is needed ,of which your assignments requires then the first
bottom up approach is advised due to its complexity of O(n2) unlike this which is O(n3);
Below is a java program to implement the pseudocode using Dynamic Programming solution storing the
correct answers to subproblems in two arrays namely pal[][] and count[][], and keeps reusing the
values stored:
import java.io.*;
import java.util.*;
public class findpalindromes
{
//java program to find the minimum cuts in palindromic partioning using top-down
approach and memoization technique
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
String s=in.next();
//String s=“madamanna”;
System.out.println("The value of Best-palindrome of string s is" + bestpal(s));
}
//this method Returns the integer representing number
// of partitioning the given string to ensure each
// part is a palindrome
static int bestpal(String strin)
{
//let length to be the length of the given string
int length=strin.length();
/* We need to create two arrays to store , compute and check if values therein are
computed and if not then we create one
count[i][j]=this represents the min no of cuts required for palindrome partitioning

of Strin[i…j];
boolean pal[i][j]= sets values to true if subtring(i.. j) is palindrome else false.
*/
int[][] count= new int[length][length];
boolean[][] pal = new boolean[length][length];
int i, j, k, len; // to use in our loops
//For every substring of length=1 is a palindrome
for (i = 0; i < length; i++)
{
pal[i][i] = true;
count[i][i] = 1;
}
/*given that len is length of the substring. Lets solve by taking into
consideration all substrings
of length beginning from len=2 to length since strings with length=1 are
palindrome.
**/
for (len = 2; len <= length; len++)
{
// In each and every substring of length len,lets allocate different
// possible beginning indexes
for (i = 0; i < length - len + 1; i++)
{
j = i + len - 1; // this becomes our end index
// If len=2, then we need to
// compare the two characters. Otherwise we need to
// check the two extreme characters and value
// of pal[i+1][j-1]
if (len == 2)
pal[i][j] = (strin.charAt(i) == strin.charAt(j));
else
pal[i][j] = (strin.charAt(i) == strin.charAt(j)) && pal[i+1][j-1];
// If our String is a palindrome, then
// count[i][j] is 1
if (pal[i][j])
count[i][j] = 1;
else
{
// now lets break the string in every possible location from i to j
// and we return the minimum breaking cost while storing and calling
the states recursively.
count[i][j] = Integer.MAX_VALUE;
for (k = i; k <= j - 1; k++)
count[i][j] = Integer.min(count[i][j],
count[i][k] + count[k+1][j] + 1);
}
}
}
// Finally lets Return the minimum breaking cost( value) for the complete
// string strin from (0..length-1).
return count[0][length-1] + 1;
}
}
References:

1. Rubinchik, M. and Shur, A.M., 2015, October. EERTREE: an efficient data structure for
processing palindromes in strings. In International Workshop on Combinatorial Algorithms (pp.
321-333). Springer, Cham.
2. Tomohiro, I., Inenaga, S. and Takeda, M., 2013. Palindrome pattern matching. Theoretical
Computer Science, 483, pp.162-170.