验证回文串
1、参考资料
https://leetcode-cn.com/problems/valid-palindrome/
2、题目要求
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
3、代码思路
我们在字符串
str
上定义双指针,
left
用于指向
str
左边的字符,
right
用于指向
str
右边的字符
在移动任意一个指针时,需要不断地向另一指针的方向移动,直到遇到一个字母或数字字符,或者两指针重合为止
然后判断
left
指针和
right
指针指向的字符是否相同,如果不相同,则表示
str
为非回文字符串,返回
false
;如果当
left == right
时,则说明
str
满足回文字符串的条件,返回
true
4、代码实现
代码
/**
* @ClassName IsPalindromeDmo
* @Description TODO
* @Author Heygo
* @Date 2020/9/1 15:06
* @Version 1.0
*/
public class IsPalindromeDmo {
public static void main(String[] args) {
boolean isPalindrome = isPalindrome("A man, a plan, a canal: Panama");
System.out.println(isPalindrome);
}
/**
* 判断字符串是否为回文字符串
* @param str 源字符串
* @return true:是回文字符串;false:不是回文字符串
*/
public static boolean isPalindrome(String str) {
// 左指针
int left = 0;
// 右指针
int right = str.length() - 1;
// 左右指针重合时,程序结束
while (left < right) {
// 如果是非字母数字的字符,则 left 右移,加上 left < right 的条件,防止 left 指针越界
while (left < right && !Character.isLetterOrDigit(str.charAt(left))) {
left++;
}
// 如果是非字母数字的字符,则 right 左移,加上 left < right 的条件,防止 right 指针越界
while (left < right && !Character.isLetterOrDigit(str.charAt(right))) {
right--;
}
// 如果左指针和右指针指向的字符相同,则左指针右移,右指针左移,进行下一组字符的判断
if (Character.toLowerCase(str.charAt(left)) == Character.toLowerCase(str.charAt(right))) {
left++;
right--;
} else {
// 否则,返回 false,表示 str 为非回文字符串
return false;
}
}
// 当 left == right 时,表示 str 回文字符串
return true;
}
}