给定一个字符串，我们必须找到需要在给定字符串的任意位置插入的不同字符的最小数量，以便最终字符串为回文。回文是一个正好等于其反转的字符串。这道题是动态规划的，所以我们先用递归的方式，然后我们去背，最后我们会看到背诵方式的表格。
递归方法
示例
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)，因为我们存储的是已经计算的结果。
立即学习“Java免费学习笔记（深入）”；
上面代码的空间复杂度是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 编程语言实现了从递归到记忆再到制表的三种方法，以查找使给定字符串成为回文所需的最小插入次数。回文是一个字符串，它正好等于它的反面，或者我们可以从前面或后面读取字符是相同的。
