fork(3) download
copy 
  1. // Dynamic Programming Solution for Palindrome Partitioning Problem
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <limits.h>
  5.  
  6. // A utility function to get minimum of two integers
  7. int min (int a, int b) { return (a < b)? a : b; }
  8.  
  9. // Returns the minimum number of cuts needed to partition a string
  10. // such that every part is a palindrome
  11. int minPalPartion(char *str)
  12. {
  13.     // Get the length of the string
  14.     int n = strlen(str);
  15.  
  16.     /* Create two arrays to build the solution in bottom up manner
  17.        C[i] = Minimum number of cuts needed for palindrome partitioning
  18.                  of substring str[0..i]
  19.        P[i][j] = true if substring str[i..j] is palindrome, else false
  20.        Note that C[i] is 0 if P[0][i] is true */
  21.     int C[n];
  22.     bool P[n][n];
  23.  
  24.     int i, j, k, L; // different looping variables
  25.  
  26.     // Every substring of length 1 is a palindrome
  27.     for (i=0; i<n; i++)
  28.     {
  29.         P[i][i] = true;
  30.     }
  31.  
  32.     /* L is substring length. Build the solution in bottom up manner by
  33.        considering all substrings of length starting from 2 to n. */
  34.     for (L=2; L<=n; L++)
  35.     {
  36.         // For substring of length L, set different possible starting indexes
  37.         for (i=0; i<n-L+1; i++)
  38.         {
  39.             j = i+L-1; // Set ending index
  40.  
  41.             // If L is 2, then we just need to compare two characters. Else
  42.             // need to check two corner characters and value of P[i+1][j-1]
  43.             if (L == 2)
  44.                 P[i][j] = (str[i] == str[j]);
  45.             else
  46.                 P[i][j] = (str[i] == str[j]) && P[i+1][j-1];
  47.         }
  48.     }
  49.  
  50.         for (i=0; i<n; i++)
  51.         {
  52.             if (P[0][i] == true)
  53.                 C[i] = 0;
  54.             else
  55.             {
  56.                 C[i] = INT_MAX;
  57.                 for(j=0;j<i;j++)
  58.                 {
  59.                     if(P[j+1][i] == true && 1+C[j]<C[i])
  60.                         C[i]=1+C[j];
  61.                 }
  62.             }
  63.         }
  64.  
  65.     // Return the min cut value for complete string. i.e., str[0..n-1]
  66.     return C[n-1];
  67. }
  68.  
  69. // Driver program to test above function
  70. int main()
  71. {
  72.    char str[] = "ababbbabbababa";
  73.    printf("Min cuts needed for Palindrome Partitioning is %d",
  74.            minPalPartion(str));
  75.    return 0;
  76. }
Success #stdin #stdout 0s 3296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Min cuts needed for Palindrome Partitioning is 3
https://ideone.com/GDggYi
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!