Un palindrome est une corde égale à son inversion. Étant donné une chaîne, nous devons trouver le nombre minimum de caractères arbitraires insérés requis pour faire de la chaîne un palindrome. Nous verrons trois approches : d'abord l'approche récursive, puis nous mémoriserons cette solution, et enfin, nous mettrons en œuvre l'approche de programmation dynamique.
#include// library for input and output #include // library to get the integer limits #include // 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; }
The minimum number of insertions required to form the palindrome is: 8
La complexité temporelle du code ci-dessus est O(2^N) car nous effectuons une sélection pour chaque insertion, où N est la taille de la chaîne donnée.
La complexité spatiale du code ci-dessus est O(N), c'est-à-dire lorsqu'il est utilisé dans des appels récursifs.
#include// library for input and output #include // library to get the integer limits #include // 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; }
The minimum number of insertions required to form the palindrome is: 8
La complexité temporelle du code ci-dessus est O(N^2) car nous stockons les résultats déjà calculés.
La complexité spatiale du code ci-dessus est O(N^2) car nous utilisons ici de l'espace supplémentaire.
#include// library for input and output #include // library to get the integer limits #include // 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; }
The minimum number of insertions required to form the palindrome is: 8
La complexité temporelle du code ci-dessus est O(N^2) car nous utilisons ici des boucles for imbriquées.
La complexité spatiale du code ci-dessus est O(N^2) car nous utilisons ici de l'espace supplémentaire.
Dans ce tutoriel, nous avons implémenté trois méthodes pour trouver le nombre minimum d'insertions requis pour faire d'une chaîne donnée un palindrome. Nous avons implémenté la méthode récursive puis l'avons mémorisée. Enfin, nous avons implémenté la méthode tabulaire ou la méthode de programmation dynamique.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
