双指针
题目要求忽略非字母数字字符，并且字母忽略大小写，因此可以使用双指针分别从字符串两端向中间扫描。
如果当前字符不是字母或数字，就直接跳过；当左右两侧都停在有效字符后，再判断它们是否相同。数字必须完全相同，字母则只需忽略大小写后相同即可。只要有一组字符不匹配，就不是回文串。
时间复杂度 $O(n)$
空间复杂度 $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
int left = 0;
int right = n - 1;
while (left < right) {
while (left < right && !isLetter(s.charAt(left)) && !isNumber(s.charAt(left))) {
left++;
}
while (left < right && !isLetter(s.charAt(right)) && !isNumber(s.charAt(right))) {
right--;
}
if (left >= right) {
break;
}
if (!isSameChar(s.charAt(left), s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
private boolean isLetter(char c) {
if (c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z') {
return true;
}
return false;
}
private boolean isNumber(char c) {
if (c >= '0' && c <= '9') {
return true;
}
return false;
}
private boolean isSameChar(char c1, char c2) {
if (isNumber(c1) && isNumber(c2)) {
return c1 == c2;
}
if (isLetter(c1) && isLetter(c2) && (c1 - c2 == 0 || c1 - c2 == 'a' - 'A' || c1 - c2 == 'A' - 'a')) {
return true;
}
return false;
}
}
|
双指针
也可以直接调用语言自带的字符判断函数，使写法更简洁。
同样用左右指针从两端向中间移动，先跳过所有非字母数字字符，再把当前位置字符统一转成小写后比较。这样就把“过滤无效字符”和“忽略大小写”都统一处理掉了。
时间复杂度 $O(n)$
空间复杂度 $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
int left = 0;
int right = n - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}
|