本文主要是介绍【双指针法】【打卡第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. 验证回文字符串 Ⅱ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!