Given a string, we have to find the minimum number of different characters that need to be inserted anywhere in the given string so that the final string is a palindrome. A palindrome is a string that is exactly equal to its reverse. This question is dynamically programmed, so we first use the recursive method, then we memorize it, and finally we will see the table of the recitation method.
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
The time complexity of the above code is O(2^N) because we make a selection for each insertion, where N is the size of the given string.
The space complexity of the above code is O(N) for recursive calls.
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
The time complexity of the above code is O(N^2), because we store the calculated results.
The space complexity of the above code is O(N^2) because we use extra space here.
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
The time complexity of the above code is O(N^2) because we use nested for loops here.
The space complexity of the above code is O(N^2) because we use extra space here.
In this tutorial, we implemented three methods, from recursion to memoization to tabulation, using the JavaScript programming language to find the minimum number of insertions required to make a given string a palindrome. A palindrome is a string that is exactly equal to its reverse, or we can read characters from the front or back that are the same.
The above is the detailed content of JavaScript program to find the minimum number of insertions that form a palindrome. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
