Programme JavaScript pour trouver le nombre minimum d'insertions qui forment un palindrome

Étant donné une chaîne, nous devons trouver le nombre minimum de caractères différents qui doivent être insérés à n'importe quelle position de la chaîne donnée pour que la chaîne finale soit un palindrome. Un palindrome est une corde exactement égale à son inverse. Cette question est programmée dynamiquement, nous utilisons donc d'abord la méthode récursive, puis nous la mémorisons, et enfin nous verrons le tableau de la méthode de récitation.

Méthode récursive

Exemple

const max = 1e5; // defining the upper limit 
// function to find the minimum of two number as it is not present in the c language 
function findMin(a, b){ 
   if(a < b){
      return a;
   } else{
       return b;
   }
}
// creating the function for finding the required answer we will make recursive calls to it 
function findAns(str,start,end){
   // base condition
   if (start > end){
      return 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 calls on 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));
   }
}
// given inputs
var str = "thisisthestring"; // given string
console.log("The minimum number of insertions required to form the palindrome is: " + findAns(str,0,str.length-1));

Sortie

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

Complexité temporelle et spatiale

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) pour les appels récursifs.

Méthode de mémoire

Exemple

const max = 1e5; // defining the upper limit 
var memo = new Array(1005); // array to store the recursion results
// function to find the minimum of two number as it is not present in the c language 
function findMin(a, b){ 
   if(a < b){
      return a;
   } else{
      return b;
   }
}  
// creating function for finding the required answer we will make recursive calls to it 
function findAns(str,start,end){
   // base condition
   if (start > end){
      return max;
   }
   else if(start == end){
       return 0;
   }
   else if (start == end - 1){
      if(str[start] == str[end]){
         return 0;
      }
      else return 1;
   }
        
   if(memo[start][end] != -1){
      return memo[start][end];
   }
        
   // check if both start and end characters are the same make calls on the 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];
}
// given inputs
var str = "thisisthestring"; // given string
// initialzie the memo array 
for(var i=0; i< 1005; i++){
   memo[i] = new Array(1005);
   for(var j = 0; j<1005; j++){
      memo[i][j] = -1;
   }
}
console.log("The minimum number of insertions required to form the palindrome is: " + findAns(str,0,str.length-1));

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N^2) car nous stockons les résultats calculés.

La complexité spatiale du code ci-dessus est O(N^2) car nous utilisons ici de l'espace supplémentaire.

Méthode de programmation dynamique

Exemple

const max = 1e5; // defining the upper limit 
var memo = new Array(1005); // array to store the recursion results
// function to find the minimum of two number as it is not present in the c language 
function findMin(a, b){ 
   if(a < b){
      return a;
   } else{
      return b;
   }
}
// creating a function for finding the required answer we will make recursive calls to it 
function findAns(str, len){
        
   // filling the table by traversing over the string 
   for (var i = 1; i < len; i++){
      for (var 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];
}
// given inputs
var str = "thisisthestring"; // given string
// initialzie the memo array 
for(var i=0; i< 1005; i++){
   memo[i] = new Array(1005);
   for(var j = 0; j<1005; j++){
      memo[i][j] = 0;
   }
}
console.log("The minimum number of insertions required to form the palindrome is: " + findAns(str,str.length));

Sortie

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

Complexité temporelle et spatiale

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.

Conclusion

Dans ce tutoriel, nous avons implémenté trois méthodes allant de la récursivité à la mémorisation en passant par la tabulation en utilisant le langage de programmation JavaScript pour trouver le nombre minimum d'insertions requises pour faire d'une chaîne donnée un palindrome. Un palindrome est une chaîne qui est exactement égale à son inverse, ou on peut lire des caractères du recto ou du verso qui sont identiques.

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!