最新公告
  • 欢迎您光临码农资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!加入我们
  • JavaScript 程序查找形成回文的最少插入次数

    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 编程语言实现了从递归到记忆再到制表的三种方法,以查找使给定字符串成为回文所需的最小插入次数。回文是一个字符串,它正好等于它的反面,或者我们可以从前面或后面读取字符是相同的。

    想要了解更多内容,请持续关注码农资源网,一起探索发现编程世界的无限可能!
    本站部分资源来源于网络,仅限用于学习和研究目的,请勿用于其他用途。
    如有侵权请发送邮件至1943759704@qq.com删除

    码农资源网 » JavaScript 程序查找形成回文的最少插入次数
    • 7会员总数(位)
    • 25846资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 292稳定运行(天)

    提供最优质的资源集合

    立即查看 了解详情