这是悦乐书的第287次更新，第304篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第155题（顺位题号是680）。给定非空字符串s，最多可以删除一个字符。 判断它是否是回文。例如：
输入：“aba”
输出：true
输入：“abca”
输出：true
说明：可以删除字符“c”让其变为回文。
注意：该字符串仅包含小写字符a-z。 字符串的最大长度为50000。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
暴力解法。首先，如果字符串长度在2以内，直接返回true。然后利用StringBuilder类，借助其reverse方法，判断是否为回文。如果上面两种情况都不满足，就使用循环，每次对原字符串进行截取，来实现删掉一位的效果，组成新的字符串来判断是否为回文。但是此解法会超时。
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 第三种解法
思路与第二种解法相似，但是比较轻便，借助双指针来实现。一左一右取字符比较，如果不等，表示遇到了需要删除的字符，同样分两种情况，删右边的一位和删左边的一位，再去判断这中间的子字符串是否为回文即可。
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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！