C program to find the minimum number of insertions to form a palindrome

A palindrome is a string equal to its reverse. Given a string, we need to find the minimum number of inserted arbitrary characters required to make the string a palindrome. We will see three approaches: first the recursive approach, then we will memoize this solution, and finally, we will implement the dynamic programming approach.

Recursive method

Example

#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits 
#include <string.h> // library for strings 
// function to find the minimum of two number 
// as it is not present in the c language 
int findMin(int a, int b){ 
   if(a < b){
      return a;
   } else{
      return b;
   }
}
// creating the function to find the required answer we will make recursive calls to it 
int findAns(char str[], int start, int end){
   // base condition
   if (start > end){
      return INT_MAX;
   }
   else if(start == end){
      return 0;
   }
   else if (start == end - 1){
      if(str[start] == str[end]){
         return 0;
      }
      else return 1;
   }	
   // check if both start and end characters are the same make callson the basis of that 
   if(str[start] == str[end]){
      return findAns(str,start+1, end-1);
   } else{
      return 1+ findMin(findAns(str,start,end-1), findAns(str,start+1,end));
   }
}
// main function 
int main(){
   char str[] = "thisisthestring"; // given string
   printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str,0,strlen(str)-1));
   return 0;
}

Output

The minimum number of insertions required to form the palindrome is: 8

Time and space complexity

The time complexity of the above code is O(2^N) because we make a selection for each insertion, where N is the size of the given string.

The space complexity of the above code is O(N), that is, it is used in recursive calls.

Memory method

Example

#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits 
#include <string.h> // library for strings 

int memo[1005][1005]; // array to store the recursion results 
// function to find the minimum of two number 
// as it is not present in the c language 
int findMin(int a, int b){ 
   if(a < b){
      return a;
   } else{
      return b;
   }
}
// creating the function to find the required answer we will make recursive calls to it 
int findAns(char str[], int start, int end){
   // base condition
   if (start > end){
      return INT_MAX;
   }
   else if(start == end){
      return 0;
   }
   else if (start == end - 1){
      if(str[start] == str[end]){
         return 0;
      }
      else return 1;
   }
   // if already have the result 
   if(memo[start][end] != -1){
      return memo[start][end];
   }	
   // check if both start and end characters are same make calls on basis of that 
    if(str[start] == str[end]){
      memo[start][end] =  findAns(str,start+1, end-1);
   } else{
        memo[start][end] =  1+ findMin(findAns(str,start,end-1), findAns(str,start+1,end));
   }
   return memo[start][end];
}
int main(){
   char str[] = "thisisthestring"; // given string	
   //Initializing the memo array 
   memset(memo,-1,sizeof(memo));
   printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str,0,strlen(str)-1));	
   return 0;
}

Output

The minimum number of insertions required to form the palindrome is: 8

Time and space complexity

The time complexity of the above code is O(N^2) because we store the calculated results.

The space complexity of the above code is O(N^2) because we use extra space here.

Dynamic programming method

Example

#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits 
#include <string.h> // library for strings 
    
// function to find the minimum of two number 
// as it is not present in the c language 
int findMin(int a, int b){ 
   if(a < b){
      return a;
   } else{
      return b;
   }
}
// creating a function to find the required answer 
int findAns(char str[], int len){
   // creating the table and initialzing it 
   int memo[1005][1005]; 
   memset(memo,0,sizeof(memo));	
   // filling the table by traversing over the string 
   for (int i = 1; i < len; i++){
      for (int start= 0, end = i; end < len; start++, end++){
         if(str[start] == str[end]){
            memo[start][end] = memo[start+1][end-1];
         } else{
              memo[start][end] = 1 + findMin(memo[start][end-1], memo[start+1][end]);
         }
      }
   }
   // return the minimum numbers of interstion required for the complete string 
      return memo[0][len-1];
}
int main(){
   char str[] = "thisisthestring"; // given string	
   // calling to the function 
   printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str, strlen(str)));	
   return 0;
}

Output

The minimum number of insertions required to form the palindrome is: 8

Time and space complexity

The time complexity of the above code is O(N^2) because we use a nested for loop here.

The space complexity of the above code is O(N^2) because we use extra space here.

in conclusion

In this tutorial, we implemented three methods to find the minimum number of insertions required to make a given string a palindrome. We implemented the recursive method and then memoized it. Finally, we implemented the tabular method or the dynamic programming method.

The above is the detailed content of C program to find the minimum number of insertions to form a palindrome. For more information, please follow other related articles on the PHP Chinese website!