You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
64 lines
1.6 KiB
C++
64 lines
1.6 KiB
C++
5 years ago
|
/*
|
||
|
|
* C++ Program to Solve Palindrome Partitioning Problem
|
||
|
|
*/
|
||
|
|
#include <iostream>
|
||
|
|
#include <cstdio>
|
||
|
|
#include <cstring>
|
||
|
|
#include <climits>
|
||
|
|
#include <cstring>
|
||
|
|
#include <cstdlib>
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
// get minimum of two integers
|
||
|
|
int min (int a, int b)
|
||
|
|
{
|
||
|
|
return (a < b)? a : b;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* Returns the minimum number of cuts needed to partition a string
|
||
|
|
* such that every part is a palindrome
|
||
|
|
*/
|
||
|
|
int minPalPartion(char *str)
|
||
|
|
{
|
||
|
|
int n = strlen(str);
|
||
|
|
int C[n][n];
|
||
|
|
bool P[n][n];
|
||
|
|
int i, j, k, L;
|
||
|
|
for (i = 0; i < n; i++)
|
||
|
|
{
|
||
|
|
P[i][i] = true;
|
||
|
|
C[i][i] = 0;
|
||
|
|
}
|
||
|
|
for (L = 2; L <= n; L++)
|
||
|
|
{
|
||
|
|
for (i = 0; i < n - L + 1; i++)
|
||
|
|
{
|
||
|
|
j = i + L - 1;
|
||
|
|
if (L == 2)
|
||
|
|
P[i][j] = (str[i] == str[j]);
|
||
|
|
else
|
||
|
|
P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1];
|
||
|
|
if (P[i][j] == true)
|
||
|
|
C[i][j] = 0;
|
||
|
|
else
|
||
|
|
{
|
||
|
|
C[i][j] = INT_MAX;
|
||
|
|
for (k = i; k <= j - 1; k++)
|
||
|
|
C[i][j] = min (C[i][j], C[i][k] + C[k + 1][j] + 1);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return C[0][n-1];
|
||
|
|
}
|
||
|
|
|
||
|
|
// Main
|
||
|
|
int main()
|
||
|
|
{
|
||
|
|
char str[] = "ababbbabbababa";
|
||
|
|
cout<<"Min cuts needed for Palindrome Partitioning is: "<<minPalPartion(str);
|
||
|
|
cout<<endl;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
Min cuts needed for Palindrome Partitioning is: 3
|