不負(fù)相思意
2018-10-11 10:15:30
給定一個(gè)字符串s,你可以從中刪除一些字符,使得剩下的串是一個(gè)回文串。如何刪除才能使得回文串最長呢?輸出需要刪除的字符個(gè)數(shù)。輸入要求:輸入數(shù)據(jù)有多組,每組包含一個(gè)字符串s,且保證:1<=s.length<=1000.輸出要求:對于每組數(shù)據(jù),輸出一個(gè)整數(shù),代表最少需要刪除的字符個(gè)數(shù)。我的思路是這樣的遍歷實(shí)例化agruguments數(shù)組之后,然后對數(shù)組進(jìn)行遍歷,如果i對應(yīng)的那個(gè)字母僅僅出現(xiàn)一次,而且arr[i-1]!=arr[i+1],那么就刪除i對應(yīng)的那個(gè)字母,然后在另個(gè)負(fù)責(zé)計(jì)數(shù)的變量里面加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]里面的這個(gè)數(shù),然后判斷他是不是0嗎?但是這樣怎么能統(tǒng)計(jì)出需要刪除的個(gè)數(shù)呢? }}
1 回答

白衣染霜花
TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超10個(gè)贊
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]
}
添加回答
舉報(bào)
0/150
提交
取消