- 驗證回文字串 Ⅱ
給定一個非空字串 s，最多洗掉一個字符，判斷是否能成為回文字串，
示例 1:
輸入: s = “aba”
輸出: true
示例 2:
輸入: s = “abca”
輸出: true
解釋: 你可以洗掉c字符，
示例 3:
輸入: s = “abc”
輸出: false
提示：
1 <= s.length <= 105
s 由小寫英文字母組成
解法：
由于該題目是判斷回文串的進階版，可以洗掉一個后判斷，那么依舊可以用我們之前的雙指標遍歷方法，只不過在洗掉一個這個條件上，我們可以另外寫一個函式判斷洗掉一個字符后，字串是否滿足回文串，
而對于洗掉一個字符后是否為回文串，需要考慮兩種情況，一種是刪左邊，一種是刪右邊，因此在判定時要呼叫兩次判定回文串的函式
代碼如下：
/**
* @param {string} s
* @return {boolean}
*/
var validPalindrome = function(s) {
let a=0,b=s.length-1;
while(a<b){
if(s[a]!=s[b]){//判斷洗掉左邊字符或洗掉右邊字符后，是否為回文串
if(judge(s,a+1,b)==true || judge(s,a,b-1)==true){//刪左邊，刪右邊，只要有一個滿足便true
return true;
}
else{//都不滿足則false
return false;
}
}
a++;
b--;
}
return true;
};
function judge(str,a,b){//判斷是否為回文串
while(a<b){
if(str[a]!=str[b])return false;
else{
a++;
b--;
}
}
return true;
}
演算法性能如圖：
可以看到時間復雜度上表現還是很不錯的
最后，附上一個小知識，對于js語言實作字串翻轉的方法：
由于字串沒reverse()方法，陣列有，那么思路就清晰了
函式式編程實作字串翻轉：
let a="abababa"
a.split("").reverse().join("")//先split切割為字串陣列，翻轉后，再將陣列中所有元素加入一個字串
如果覺得該篇文章對你思路有啟發，請不要忘記點擊右下角的大拇指~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/290673.html
標籤：其他
上一篇：React基礎講解
下一篇：前端開發需要學習什么