本文主要是介绍【双指针法】【打卡第37天】leetCode之Java实现:680. 验证回文字符串 Ⅱ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
2、算法分析
之前做的是判断一个链表是否是回文链表，比较简单。
本题题意：最多删除其中的一个字符，判断是否是回文链表。
所谓的回文字符串，是指具有左右对称特点的字符串，例如 "abcba" 就是一个回文字符串。
使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。
下面是判断回文链表:
本题的关键是处理删除一个字符。从字符串两端判断。
在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。
在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。
在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。
过程如下：
小结：
若左右指针指向的值相等，那么左右指针同时相向移动一个指针。
若左右指针指向的值不等，那么左指针或者右指针多移动一个指针，再次判断。
3、代码实现
class Solution {public boolean validPalindrome(String s) {if(s == null){return false;}int i = 0,j = s.length() - 1;while(i < j){if(s.charAt(i) != s.charAt(j)){// 如果左右不对称的话，左指针往右移动，右指针往左移动，分别进行判断return isSame(s,i+1,j) || isSame(s,i,j-1);}// 如果相等的话，左指针往右移动一个距离，右指针往左移动一个距离i++;j--;}// 前面的循环和递归如果正常结束，返回true，直接方法结束，如果期间返回false，方法也结束。最后true是不起作用的return true;}// 判断是否对称public boolean isSame(String s,int i,int j){while(i < j){if(s.charAt(i++) != s.charAt(j--)){return false;}}return true;}
}这篇关于【双指针法】【打卡第37天】leetCode之Java实现:680. 验证回文字符串 Ⅱ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
