【問題描述】[第680題][驗證回文字符串Ⅱ][簡單]

給定一個非空字符串 s，最多刪除一個字符。判斷是否能成為回文字符串。示例 1:輸入: "aba" 輸出: True 示例 2:輸入: "abca" 輸出: True 解釋: 你可以刪除c字符。 注意:字符串只包含從 a-z 的小寫字母。字符串的最大長度是50000。

【解答思路】

考慮最樸素的方法：首先判斷原串是否是回文串，如果是，就返回 true；如果不是，則枚舉每一個位置作為被刪除的位置，再判斷剩下的字符串是否是回文串。這種做法的漸進時間復雜度是 O(n^2)的，會超出時間限制。

首先考慮如果不允許刪除字符，如何判斷一個字符串是否是回文串。常見的做法是使用雙指針。定義左右指針，初始時分別指向字符串的第一個字符和最后一個字符，每次判斷左右指針指向的字符是否相同，如果不相同，則不是回文串；如果相同，則將左右指針都往中間移動一位，直到左右指針相遇，則字符串是回文串。

在允許最多刪除一個字符的情況下，同樣可以使用雙指針，通過貪心算法實現。初始化兩個指針 low 和 high 分別指向字符串的第一個字符和最后一個字符。每次判斷兩個指針指向的字符是否相同，如果相同，則更新指針，令 low = low + 1 和 high = high - 1，然后判斷更新后的指針范圍內的子串是否是回文字符串。如果兩個指針指向的字符不同，則兩個字符中必須有一個被刪除，此時我們就分成兩種情況：即刪除左指針對應的字符，留下子串 s[low + 1], s[low + 1], …, s[high]，或者刪除右指針對應的字符，留下子串 s[low], s[low + 1], …, s[high - 1]。當這兩個子串中至少有一個是回文串時，就說明原始字符串刪除一個字符之后就以成為回文串。

1. 貪心算法

時間復雜度：O(N^2) 空間復雜度：O(1)

class Solution {public boolean validPalindrome(String s) {int low = 0, high = s.length() - 1;while (low < high) {char c1 = s.charAt(low), c2 = s.charAt(high);if (c1 == c2) {low++;high--;} else {boolean flag1 = true, flag2 = true;for (int i = low, j = high - 1; i < j; i++, j--) {char c3 = s.charAt(i), c4 = s.charAt(j);if (c3 != c4) {flag1 = false;break;}}for (int i = low + 1, j = high; i < j; i++, j--) {char c3 = s.charAt(i), c4 = s.charAt(j);if (c3 != c4) {flag2 = false;break;}}return flag1 || flag2;}}return true;} }

2. 遞歸算法

時間復雜度：O(N) 空間復雜度：O(1)

public boolean validPalindrome(String s) {int front = 0;int end = s.length() - 1;// < 符號，中間一個字符不影響回文與否while (front < end) {if (s.charAt(front) != s.charAt(end)) {return validPalindromeHelper(s, front + 1, end) || validPalindromeHelper(s, front, end - 1);}front++;end--;}return true;}public boolean validPalindromeHelper(String s, int front, int end) {while (front < end) {if (s.charAt(front) != s.charAt(end)) {return false;}front++;end--;}return true;}

【總結】

1. 數組題目

• 暴力思考優化
• 考慮清楚邊界 防止溢出
• 多立flag
• 遞歸解決

2. 判斷回文串模板

public boolean validPalindromeHelper(String s, int front, int end) {while (front < end) {if (s.charAt(front) != s.charAt(end)) {return false;}front++;end--;}return true;}

3.比較字符串中某些位置是否相等

**方法一：Java charAt() 方法
// s.charAt(i) 每次都會檢查數組下標越界
public char charAt(int index)

方法二：轉換成字符數組再用下標進行判斷

char[] charArray = s.toCharArray();

轉載鏈接：https://leetcode-cn.com/problems/valid-palindrome-ii/solution/yan-zheng-hui-wen-zi-fu-chuan-ii-by-leetcode-solut/

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第680题][验证回文字符串Ⅱ][贪心][递归]的全部內容，希望文章能夠幫你解決所遇到的問題。

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