题目
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
题目描述:可以删除一个字符,判断是否能构成回文字符串。
https://leetcode-cn.com/problems/valid-palindrome-ii/description/
分析
所谓的回文字符串,是指具有左右对称特点的字符串,例如 "abcba" 就是一个回文字符串。
使用双指针可以很容易判断一个字符串是否是回文字符串:令一个指针从左到右遍历,一个指针从右到左遍历,这两个指针同时移动一个位置,每次都判断两个指针指向的字符是否相同,如果都相同,字符串才是具有左右对称性质的回文字符串。
本题的关键是处理删除一个字符。在使用双指针遍历字符串时,如果出现两个指针指向的字符不相等的情况,我们就试着删除一个字符,再判断删除完之后的字符串是否是回文字符串。
在判断是否为回文字符串时,我们不需要判断整个字符串,因为左指针左边和右指针右边的字符之前已经判断过具有对称性质,所以只需要判断中间的子字符串即可。
在试着删除字符时,我们既可以删除左指针指向的字符,也可以删除右指针指向的字符。
代码
正确
public boolean validPalindrome(String s) {
char[] str = s.toCharArray();
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (str[i] != str[j]) {
return isPalindrome(str, i + 1, j) || isPalindrome(str, i, j - 1);//分支
}
}
return true;//如果没有分支
}
private boolean isPalindrome(char[] str, int i, int j) {
while (i < j) {
if (str[i++] != str[j--]) {//注意 j-- 不小心打错饿了
return false;
}
}
return true;
}
反思
错误解法
思路有问题,考虑的不全 很暴力 红了五次 出一次bug 修复一下,,
致命问题 只知道当前这一步 和下一步可以成功 但是后续的能否成功不知道 万一 第一个if的是 后续的不回文 第二个的是回文就糟糕了
ebcbb ececabbacec bbcbe
删除 e c都可以 先判断的就可能是死路 所以【在删除之后 重新当做的字符串开始判断】 如正解
public boolean error_validPalindrome(String s) {
char[] str = s.toCharArray();
int i = 0, j = s.length() - 1;
boolean flag = true;
while (i <= j) {
if ((str[i] == str[j])) {
i++;
j--;
} else if (flag) { //致命问题 只知道当前这一步 和下一步可以成功 但是后续的能否成功不知道 万一 第一个if的是 后续的不回文 第二个的是回文就糟糕了
//ebcbb ececabbacec bbcbe 删除 e c都可以 先判断的就可能是死路 所以【在删除之后 重新当做的字符串开始判断】
if (j - 1 >= i && str[i] == str[j - 1]) {//可以删去
i++;
j -= 2;
flag = false;
} else if (i + 1 <= j && str[i + 1] == str[j]) {//i删去
j--;
i += 2;
flag = false;
} else
return false;
} else {
return false;
}
}
return true;
}
本文地址:https://dxoca.cn/Algorithm/360.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。