這是悅樂書的第287次更新，第304篇原創(chuàng)

01 看題和準備

今天介紹的是LeetCode算法題中Easy級別的第155題（順位題號是680）。給定非空字符串s，最多可以刪除一個字符。 判斷它是否是回文。例如：

輸入：“aba”
輸出：true

輸入：“abca”
輸出：true
說明：可以刪除字符“c”讓其變?yōu)榛匚摹?/p>

注意：該字符串僅包含小寫字符a-z。 字符串的最大長度為50000。

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測試。

02 第一種解法

暴力解法。首先，如果字符串長度在2以內，直接返回true。然后利用StringBuilder類，借助其reverse方法，判斷是否為回文。如果上面兩種情況都不滿足，就使用循環(huán)，每次對原字符串進行截取，來實現(xiàn)刪掉一位的效果，組成新的字符串來判斷是否為回文。但是此解法會超時。

public boolean validPalindrome(String s) {if (s.length() <= 2) {return true;}StringBuilder sb = new StringBuilder(s);String ss = sb.reverse().toString();if (s.equals(ss)) {return true;}for (int i=0; i<s.length(); i++) {if (i == 0) {if (isPalindrome(s.substring(1, s.length()))) {return true;}} else if (i < s.length()-1) {if (isPalindrome(s.substring(0, i)+ s.substring(i+1, s.length()))) {return true;}} else if (i == s.length()-1) {if (isPalindrome(s.substring(0, s.length()-1))) {return true;}}}return false; }public boolean isPalindrome(String ss){StringBuilder sb = new StringBuilder(ss);String sss = sb.reverse().toString();if (ss.equals(sss)) {return true;}return false; }

03 第二種解法

第一種解法會超時，因為考慮了所有可能存在的多余的那個字符，但是我們真的需要考慮那么多嗎？因為題目說了，只有一次刪除字符的機會，那么我們在處理的時候，只處理一種情況就好，不符合就直接返回false。

依舊使用截取字符串的方式，如果遇到左右字符不對稱的情況，就表示遇到了多余的字符，此時需要考慮是刪掉左邊的還是右邊的？只要兩個中符合一個就可以返回true，所以用或連接。將左右兩字符不等的索引范圍內的字符串進行截取，一個后面少截取一位，一個前面少截取一位，判斷截取的字符串是否為回文。

public boolean validPalindrome(String s) {if (s.length() <= 2) {return true;}StringBuilder sb = new StringBuilder(s);String ss = sb.reverse().toString();if (s.equals(ss)) {return true;}for (int i=0; i<s.length()/2; i++) {if (s.charAt(i) != s.charAt(s.length()-1-i)) {return isPalindrome(s.substring(i, s.length()-1-i)) || isPalindrome(s.substring(i+1, s.length()-i));}}return true; }public boolean isPalindrome(String ss){StringBuilder sb = new StringBuilder(ss);String sss = sb.reverse().toString();if (ss.equals(sss)) {return true;}return false; }

04 第三種解法

思路與第二種解法相似，但是比較輕便，借助雙指針來實現(xiàn)。一左一右取字符比較，如果不等，表示遇到了需要刪除的字符，同樣分兩種情況，刪右邊的一位和刪左邊的一位，再去判斷這中間的子字符串是否為回文即可。

public boolean validPalindrome(String s) {// 使用雙指針int left = 0;int right = s.length()-1;while (left < right) {// 如果左右指針所在的字符不相等，那就刪掉右邊的或者刪掉左邊的字符，再判斷if (s.charAt(left) != s.charAt(right)) {return isPalindrome(s, left, right-1) || isPalindrome(s, left+1, right);}left++;right--;}return true; }// 輔助方法，判斷一個字符串在（left,right）內是否為回文 public boolean isPalindrome(String s, int left, int right){while (left < right) {if (s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true; }

05 小結

算法專題目前已日更超過四個月，算法題文章155+篇，公眾號對話框回復【數(shù)據(jù)結構與算法】、【算法】、【數(shù)據(jù)結構】中的任一關鍵詞，獲取系列文章合集。

以上就是全部內容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發(fā)就是對我最大的回報和支持！

轉載于:https://www.cnblogs.com/xiaochuan94/p/10596796.html

總結

以上是生活随笔為你收集整理的LeetCode算法题-Valid Palindrome II（Java实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。