JavaScript 程式找出形成回文的最少插入次數

給定一個字串，我們必須找到需要在給定字串的任意位置插入的不同字元的最小數量，以便最終字串為回文。回文是一個剛好等於其反轉的字串。這題是動態規劃的，所以我們先用遞歸的方式，然後我們去背，最後我們會看到背誦方式的表格。

遞歸方法

範例

#

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

輸出

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

時間與空間複雜度

上述程式碼的時間複雜度為 O(2^N)，因為我們為每次插入進行選擇，其中 N 是給定字串的大小。

上述程式碼的空間複雜度為O(N)，用於遞迴呼叫。

記憶方法

範例

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

輸出

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

時間與空間複雜度

上述程式碼的時間複雜度是O(N^2)，因為我們儲存的是已經計算出來的結果。

上面程式碼的空間複雜度是O(N^2)，因為我們在這裡使用了額外的空間。

動態規劃方法

範例

#

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

輸出

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

時間與空間複雜度

上面程式碼的時間複雜度是 O(N^2)，因為我們在這裡使用嵌套的 for 迴圈。

上面程式碼的空間複雜度是O(N^2)，因為我們在這裡使用了額外的空間。

結論

在本教程中，我們使用 JavaScript 程式語言實作了從遞歸到記憶再到製表的三種方法，以查找使給定字串成為回文所需的最小插入次數。回文是一個字串，它剛好等於它的反面，或者我們可以從前面或後面讀取字元是相同的。

以上是JavaScript 程式找出形成回文的最少插入次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！