Palindrome Partitioning Problem in C++

This C++ Program Solves Palindrome Partitioning Problem.

Here is source code of the C++ Program to solve Palindrome Partitioning Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Solve Palindrome Partitioning Problem
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <climits>
  8. #include <cstring>
  9. #include <cstdlib>
  10. using namespace std;
  11.  
  12. // get minimum of two integers
  13. int min (int a, int b)
  14. {
  15.     return (a < b)? a : b;
  16. }
  17.  
  18. /* Returns the minimum number of cuts needed to partition a string
  19.  * such that every part is a palindrome
  20.  */
  21. int minPalPartion(char *str)
  22. {
  23.     int n = strlen(str);
  24.     int C[n][n];
  25.     bool P[n][n];
  26.     int i, j, k, L;
  27.     for (i = 0; i < n; i++)
  28.     {
  29.         P[i][i] = true;
  30.         C[i][i] = 0;
  31.     }
  32.     for (L = 2; L <= n; L++)
  33.     {
  34.         for (i = 0; i < n - L + 1; i++)
  35.         {
  36.             j = i + L - 1;
  37.             if (L == 2)
  38.                 P[i][j] = (str[i] == str[j]);
  39.             else
  40.                 P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1];
  41.             if (P[i][j] == true)
  42.                 C[i][j] = 0;
  43.             else
  44.             {
  45.                 C[i][j] = INT_MAX;
  46.                 for (k = i; k <= j - 1; k++)
  47.                     C[i][j] = min (C[i][j], C[i][k] + C[k + 1][j] + 1);
  48.             }
  49.         }
  50.     }
  51.     return C[0][n-1];
  52. }
  53.  
  54. // Main
  55. int main()
  56. {
  57.     char str[] = "ababbbabbababa";
  58.     cout<<"Min cuts needed for Palindrome Partitioning is: "<<minPalPartion(str);
  59.     cout<<endl;
  60.     return 0;
  61. }

$ g++ palindrome_partitioning.cpp
$ a.out
 
Min cuts needed for Palindrome Partitioning is: 3
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.