C-Programm, um die Mindestanzahl von Einfügungen zu ermitteln, um ein Palindrom zu bilden

Ein Palindrom ist eine Zeichenfolge, die ihrer Umkehrung entspricht. Bei einer gegebenen Zeichenfolge müssen wir die Mindestanzahl eingefügter beliebiger Zeichen ermitteln, die erforderlich ist, um die Zeichenfolge in ein Palindrom zu verwandeln. Wir werden drei Ansätze sehen: Zuerst den rekursiven Ansatz, dann werden wir uns diese Lösung merken und schließlich werden wir den dynamischen Programmieransatz implementieren.

Rekursive Methode

Beispiel

#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;
}

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(2^N), da wir für jede Einfügung eine Auswahl treffen, wobei N die Größe der angegebenen Zeichenfolge ist.

Die räumliche Komplexität des obigen Codes beträgt O(N), wenn er in rekursiven Aufrufen verwendet wird.

Speichermethode

Beispiel

#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;
}

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N^2), da wir die bereits berechneten Ergebnisse speichern.

Die Speicherplatzkomplexität des obigen Codes beträgt O(N^2), da wir hier zusätzlichen Speicherplatz verwenden.

Dynamische Programmiermethode

Beispiel

#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;
}

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N^2), da wir hier verschachtelte for-Schleifen verwenden.

Die Speicherplatzkomplexität des obigen Codes beträgt O(N^2), da wir hier zusätzlichen Speicherplatz verwenden.

Fazit

In diesem Tutorial haben wir drei Methoden implementiert, um die Mindestanzahl von Einfügungen zu ermitteln, die erforderlich sind, um aus einer bestimmten Zeichenfolge ein Palindrom zu machen. Wir haben die rekursive Methode implementiert und sie dann auswendig gelernt. Schließlich haben wir die tabellarische Methode oder die dynamische Programmiermethode implementiert.

Das obige ist der detaillierte Inhalt vonC-Programm, um die Mindestanzahl von Einfügungen zu ermitteln, um ein Palindrom zu bilden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!