JavaScript-Programm zum Ermitteln der Mindestanzahl von Einfügungen, die ein Palindrom bilden

Bei einer gegebenen Zeichenfolge müssen wir die Mindestanzahl verschiedener Zeichen ermitteln, die an einer beliebigen Position der angegebenen Zeichenfolge eingefügt werden müssen, damit die endgültige Zeichenfolge ein Palindrom ist. Ein Palindrom ist eine Zeichenfolge, die genau ihrer Umkehrung entspricht. Diese Frage ist dynamisch programmiert, daher verwenden wir zuerst die rekursive Methode, merken sie uns dann und sehen schließlich die Tabelle der Rezitationsmethode.

Rekursive Methode

Beispiel

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));

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) für rekursive Aufrufe.

Speichermethode

Beispiel

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));

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 berechneten Ergebnisse speichern.

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

Dynamische Programmiermethode

Beispiel

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));

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 von der Rekursion über die Memoisierung bis zur Tabellierung mithilfe der Programmiersprache JavaScript implementiert, um die Mindestanzahl von Einfügungen zu ermitteln, die erforderlich sind, um eine bestimmte Zeichenfolge in ein Palindrom zu verwandeln. Ein Palindrom ist eine Zeichenfolge, die genau ihrer Rückseite entspricht, oder wir können Zeichen von vorne oder hinten lesen, die gleich sind.

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