我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 680. 驗證回文字串 Ⅱ
題目
給定一個非空字串 s，最多洗掉一個字符，判斷是否能成為回文字串，
示例 1:
輸入: "aba"
輸出: True
示例 2:
輸入: "abca"
輸出: True
解釋: 你可以洗掉c字符，
注意:
- 字串只包含從 a-z 的小寫字母，
- 字串的最大長度是50000，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/valid-palindrome-ii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
至多洗掉一個，那么左右指標夾逼驗證時有以下三種情況：
- 無需洗掉；
- 遇到了不等，洗掉左邊的一個字符，繼續驗證；
- 遇到了不等，洗掉右邊的一個字符，繼續驗證；
三種情況除了初始指標位置區別外驗證的模式相同；
思路1-記錄指標的位置，提煉驗證模式方法
最多需要進行三次模式驗證，但是三次模式驗證的指標起始位置需要記錄；
指定兩個變數記錄指標的位置：
- 首次驗證若失敗，則下面兩個起始指標均為當前指標位置：
- 左指標右移一步繼續驗證，若驗證失敗；
- 右指標左移一步繼續驗證；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
思路2-遞回驗證
首次驗證為遞回的第一層，洗掉左或右一個字符為遞回的第二層，所以遞回需要嚴格控制只遞回到第二層，設計使用一個boolean變數控制；
詳見代碼；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $ 堆疊的深度為2，常數級
思路3-直接在單個方法內一個while內解決
在首次驗證失敗時，需要驗證左洗掉或者右洗掉，這里的思路是，先嘗試左洗掉，若左洗掉驗證失敗，則在當前指標位置基礎上讓左指標向左回退一個位置，右指標前左進一個位置再繼續驗證，平衡掉先刪左時多右移動的距離；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月19日 上午12:24:57
* @Description: 680. 驗證回文字串 Ⅱ
*
*/
public class LeetCode_0680 {
}
class Solution_0680 {
/**
* @author: ZhouJie
* @date: 2020年5月19日 上午12:25:24
* @param: @param s
* @param: @return
* @return: boolean
* @Description: 1-兩遍指標遍歷，記錄指標的位置，因為總共有三次機會去驗證是否可改造成回文；
*
*/
private int start = 0;
private int end = 0;
public boolean validPalindrome_1(String s) {
end = s.length() - 1;
if (!check(s)) {
int ss = start, ee = end;
start++;
if (!check(s)) {
start = ss;
end = ee;
end--;
return check(s);
}
}
return true;
}
private boolean check(String s) {
if (start > end) {
return false;
} else {
while (start <= end) {
if (s.charAt(start) == s.charAt(end)) {
start++;
end--;
} else {
return false;
}
}
return true;
}
}
/**
* @author: ZhouJie
* @date: 2020年5月19日 上午12:52:52
* @param: @param s
* @param: @return
* @return: boolean
* @Description: 2-遞回驗證，控制只遞回兩層；
*
*/
public boolean validPalindrome_2(String s) {
return check(s, 0, s.length() - 1, true);
}
private boolean check(String s, int start, int end, boolean f) {
while (start < end) {
if (s.charAt(start) == s.charAt(end)) {
start++;
end--;
} else {
// 若是首次，則進行洗掉左或右再進行驗證，否則說明無法改造為回文
return f && (check(s, start + 1, end, false) || check(s, start, end - 1, false));
}
}
return true;
}
/**
* @author: ZhouJie
* @date: 2020年5月19日 上午1:09:12
* @param: @param s
* @param: @return
* @return: boolean
* @Description: 3-單個方法內增加變數解決；
*
*/
public boolean validPalindrome_3(String s) {
int left = 0, right = s.length() - 1;
boolean leftDelete = true, rightDelete = true;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
// 嘗試洗掉左邊
if (leftDelete) {
left++;
leftDelete = false;
// 嘗試洗掉右邊，此時左邊要回退一個字符
} else if (rightDelete) {
left--;
right--;
rightDelete = false;
} else {
return false;
}
}
}
return true;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/189840.html
標籤：Java