一道腾讯的算法题

给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?
输出需要删除的字符个数。
输入要求:输入数据有多组,每组包含一个字符串s,且保证:1<=s.length<=1000.
输出要求:对于每组数据,输出一个整数,代表最少需要删除的字符个数。

我的思路是这样的遍历实例化agruguments数组之后,然后对数组进行遍历,如果i对应的那个字母仅仅出现一次,而且arr[i-1]!=arr[i+1],那么就删除i对应的那个字母,然后在另个负责计数的变量里面加1。
可是看完答案我只能看懂一部分,求各位大大解答一下。

function slect(){
    var arr=new Array();
     arr=Array.prototype.slipt(arguments);
     for(var i=0;i<arr.length;i++){
         if(arr[i])//这句是什么意思?难道不是取出arr[i]里面的这个数,然后判断他是不是0吗?但是这样怎么能统计出需要删除的个数呢?
     }
}
阅读 4.3k
1 个回答
const minCut = function(s) {
    const n = s.length;
    const cut = [];
    for (let i = 0; i <= n; i++) cut[i] = i - 1;
    for (let i = 0; i < n; i++) {
        for (let j = 0; i - j >= 0 && i + j < n && s[i - j] == s[i + j]; j++)
            cut[i + j + 1] = Math.min(cut[i + j + 1], 1 + cut[i - j]);
        for (let j = 1; i - j + 1 >= 0 && i + j < n && s[i - j + 1] == s[i + j]; j++) // even length palindrome
            cut[i + j + 1] = Math.min(cut[i + j + 1], 1 + cut[i - j + 1]);
    }
    return cut[n]
}
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题