891. 有效回文 II
给一个非空字符串
s
,你最多可以删除一个字符。判断是否可以把它变成回文串。
样例
样例 1:
输入: s = "aba"
输出: true
解释: 原本就是回文串
样例 2:
输入: s = "abca"
输出: true
解释: 删除 'b' 或 'c'
样例 3:
输入: s = "abc"
输出: false
解释: 删除任何一个字符都不能使之变成回文串
注意事项
-
给定的字符串只包含小写字母
-
字符串的长度最大为 50000
public class Solution {
/**
* @param s: a string
* @return boolean: whether you can make s a palindrome by deleting at most one character
*/
public boolean validPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return isRe(s,i,j - 1)||isRe(s,i+1,j );
}
i++;
j--;
}
return true;
}
private boolean isRe(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j) ) {
return false;
}
i++;
j--;
}
return true;
}
}