Palindrome Partitioning in C++

Suppose we have one input string, a partitioning of that string is palindrome partitioning, when every substring of the partition is a palindrome. In this section, we have to find the minimum cuts are needed to palindrome partitioning the given string. So if the string is like “ababbbabbababa” Minimum cut to partition as palindrome. Here 3 cuts are needed. The palindromes are: a | babbbab | b | ababa

To solve this, we will follow these steps −

• n := length of str
• define cut matrix and pal matrix each of order n x n
• for i := 0 to n, do
  • pal[i, i] := true and cut[i, i] := 0
• for len in range 2 to n, do
  • for i in range 0 to n – len, do
    • j := i + len – 1
    • if len = 2, then
    • if str[i] = str[j], then pal[i, j] := true
    • else when str[i] = str[j] and pal[i+1, j-1] ≠ 0 pal[i, j] := true
    • if pal[i, j] is true, then cut[i, j] := 0
    • else
      • cut[i, j] := ∞
      • for k in range i to j-1, do
        • cut[i, j] := minimum of cut[i, j] and (cut[i, k]+ cut[k+1, j+1]+1)
• return cut[0, n-1]

Example

Let us see the following implementation to get better understanding −

#include <iostream> #include <climits> using namespace std; int min (int a, int b){    return (a < b)? a : b; } int minPalPartion(string str){    int n = str.size();    int cut[n][n];    bool pal[n][n]; //true when palindrome present for i to j th element    for (int i=0; i<n; i++){       pal[i][i] = true; //substring of length 1 is plaindrome       cut[i][i] = 0;    }    for (int len=2; len<=n; len++){       for (int i=0; i<n-len+1; i++){//find all substrings of length len       int j = i+len-1; // Set ending index       if (len == 2) //for two character string          pal[i][j] = (str[i] == str[j]);       else //for string of more than two characters          pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];       if (pal[i][j] == true)          cut[i][j] = 0;       else{          cut[i][j] = INT_MAX; //initially set as infinity          for (int k=i; k<=j-1; k++)             cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j]+1);          }       }    }    return cut[0][n-1]; } int main(){    string str= "ababbbabbababa";    cout << "Min cuts for Palindrome Partitioning is: "<<minPalPartion(str); }

Input

ababbbabbababa

Output

Min cuts for Palindrome Partitioning is: 3