Program JavaScript untuk mencari bilangan sisipan minimum yang membentuk palindrom-tutorial js-php.cn

Program JavaScript untuk mencari bilangan sisipan minimum yang membentuk palindrom

WBOY

Lepaskan： 2023-08-24 16:41:02

ke hadapan

1023 orang telah melayarinya

JavaScript 程序查找形成回文的最少插入次数

Diberi rentetan, kita perlu mencari bilangan minimum aksara berbeza yang perlu disisipkan pada mana-mana kedudukan rentetan yang diberikan supaya rentetan akhir ialah palindrom. Palindrom ialah rentetan yang betul-betul sama dengan kebalikannya. Soalan ini diprogramkan secara dinamik, jadi kita mula-mula menggunakan kaedah rekursif, kemudian kita menghafalnya, dan akhirnya kita akan melihat jadual kaedah tilawah.

Kaedah rekursif

Contoh

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

Salin selepas log masuk

Output

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

Salin selepas log masuk

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(2^N) kerana kami membuat pilihan untuk setiap sisipan, dengan N ialah saiz rentetan yang diberikan.

Kerumitan ruang kod di atas ialah O(N) untuk panggilan rekursif.

Kaedah ingatan

Contoh

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

Salin selepas log masuk

Output

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

Salin selepas log masuk

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N^2) kerana kami menyimpan hasil yang dikira.

Kerumitan ruang kod di atas ialah O(N^2) kerana kami menggunakan ruang tambahan di sini.

Kaedah pengaturcaraan dinamik

Contoh

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

Salin selepas log masuk

Output

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

Salin selepas log masuk

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N^2) kerana kami menggunakan gelung bersarang di sini.

Kerumitan ruang kod di atas ialah O(N^2) kerana kami menggunakan ruang tambahan di sini.

Kesimpulan

Dalam tutorial ini, kami melaksanakan tiga kaedah daripada rekursi kepada penghafalan kepada penjadualan menggunakan bahasa pengaturcaraan JavaScript untuk mencari bilangan sisipan minimum yang diperlukan untuk menjadikan rentetan tertentu sebagai palindrom. Palindrom ialah rentetan yang betul-betul sama dengan kebalikannya, atau kita boleh membaca aksara dari hadapan atau belakang yang sama.

Atas ialah kandungan terperinci Program JavaScript untuk mencari bilangan sisipan minimum yang membentuk palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!