資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學查詢構成迴文串所需最小插入次數的 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 程式語言實現了從遞迴到記憶化再到表格化的三種方法，以查詢使給定字串成為迴文串所需的最小插入次數。迴文串是一個與自身反轉相同的字串，或者我們可以從前面或後面讀取字元，結果都相同。
更新於：2023年7月12日
瀏覽量：136
廣告