fork download
copy 
  1. // A Dynamic Programming based program to find minimum number
  2. // insertions needed to make a string palindrome
  3. #include <stdio.h>
  4. #include <string.h>
  5.  
  6. // A utility function to find minimum of two integers
  7. int min(int a, int b)
  8. {   return a < b ? a : b;  }
  9.  
  10. // A DP function to find minimum number of insersions
  11. int findMinInsertionsDP(char str[], int n)
  12. {
  13.     // Create a table of size n*n. table[i][j] will store
  14.     // minumum number of insertions needed to convert str[i..j]
  15.     // to a palindrome.
  16.     int table[n][n], l, h, gap;
  17.  
  18.     // Initialize all table entries as 0
  19.     memset(table, 0, sizeof(table));
  20.  
  21.     // Fill the table
  22.     for (gap = 1; gap < n; ++gap)
  23.         for (l = 0, h = gap; h < n; ++l, ++h)
  24.             table[l][h] = (str[l] == str[h])? table[l+1][h-1] :
  25.                           (min(table[l][h-1], table[l+1][h]) + 1);
  26.  
  27.     // Return minimum number of insertions for str[0..n-1]
  28.     return table[0][n-1];
  29. }
  30.  
  31. // Driver program to test above function.
  32. int main()
  33. {
  34.     char str[] = "999";
  35.     printf("%d", findMinInsertionsDP(str, strlen(str)));
  36.     return 0;
  37. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mhoG3Q
language:
C++14 (gcc 8.3)
created:
7 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!