给定一个字符串，我们必须找到需要在给定字符串的任意位置插入的不同字符的最小数量，以便最终字符串为回文。回文是一个正好等于其反转的字符串。这道题是动态规划的，所以我们先用递归的方式，然后我们去背，最后我们会看到背诵方式的表格。
递归方法示例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 inputsvar str = thisisthestring; // given stringconsole.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 inputsvar 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 inputsvar 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 程序查找形成回文的最少插入次数的详细内容。