文章目录
一、题目描述
1.1 题目
-
验证回文串
-
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
-
说明：本题中，我们将空字符串定义为有效的回文串。
-
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
- 示例 2:
输入: "race a car"
输出: false
1.2 知识点
- 双指针
1.3 题目链接
二、解题思路
2.1 解题思路
解题的思路比较简单，首先将字符串中的非法字符（除 0-9 a-z A-z 以外的字符）替换掉，然后将大写字母转换为小写字母，便于后续的比较，最后使用双指针从从两端向中间边移动边对比即可。
这里多说一句，其实也可以不进行预处理（将非法字符替换掉），可以在双指针移动比较的过程中进行替换，这样就可以在一遍遍历的情况下完成验证。还有就是对于评论中提供的方法二，代码简洁了很多，但是效率却是方法一的十多倍，因此简洁的代码不意味着高效率。
三、实现代码
3.1 代码实现一（2ms）
class Solution {
public boolean isPalindrome(String s) {
char[] chars = s.toCharArray();
int start = 0, end = 0;
// 替换非法字符
for (int i = 0; i < chars.length; i++) {
if ((chars[i] >= '0' && chars[i] <= '9') || (chars[i] >= 'a' && chars[i] <= 'z'))
chars[end++] = chars[i];
else if (chars[i] >= 'A' && chars[i] <= 'Z')
chars[end++] = (char) (chars[i] - 'A' + 'a');
}
end--;
// 验证回文串
while (start < end) {
if (chars[start] != chars[end]) return false;
start++;
end--;
}
return true;
}
}
3.2 代码实现二（25ms）
class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0)
return true;
String str = s.replaceAll("[^0-9a-zA-Z]", "").toLowerCase();
for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
if (str.charAt(i) != str.charAt(j))
return false;
}
return true;
}
}