题目描述
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
本题中，将空字符串定义为有效的 回文串 。
示例 1:
输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串
提示：
1 <= s.length <= 2 * 105- 字符串
s 由 ASCII 字符组成
注意：本题与主站 125 题相同： https://leetcode.cn/problems/valid-palindrome/
解法
方法一：双指针
我们定义两个指针 $i$ 和 $j$，初始时分别指向字符串的首尾位置，每次判断两个指针指向的字符是否为数字或字母，如果两个指针指向的字符都为数字或字母时，判断两个指针指向的字符是否相同（忽略大小写），如果不相同则返回 false，否则将两个指针向中间移动一位，直到两个指针相遇时返回 true。
时间复杂度 $O(n)$，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def isPalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if s[i].lower() != s[j].lower():
return False
i, j = i + 1, j - 1
return True
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
++i;
}
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
--j;
}
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
return false;
}
++i;
--j;
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public:
bool isPalindrome(string s) {
int i = 0, j = s.size() - 1;
while (i < j) {
while (i < j && !isalnum(s[i])) {
++i;
}
while (i < j && !isalnum(s[j])) {
--j;
}
if (tolower(s[i]) != tolower(s[j])) {
return false;
}
++i;
--j;
}
return true;
}
};
|
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 | func isPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
for i < j && !isalnum(s[i]) {
i++
}
for i < j && !isalnum(s[j]) {
j--
}
if tolower(s[i]) != tolower(s[j]) {
return false
}
i, j = i+1, j-1
}
return true
}
func tolower(b byte) byte {
if b >= 'A' && b <= 'Z' {
return b - 'A' + 'a'
}
return b
}
func isalnum(b byte) bool {
return b >= '0' && b <= '9' ||
b >= 'a' && b <= 'z' ||
b >= 'A' && b <= 'Z'
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | function isPalindrome(s: string): boolean {
const str = s.replace(/[^a-zA-Z0-9]/g, '');
let l = 0;
let r = str.length - 1;
while (l < r) {
if (str[l].toLocaleLowerCase() !== str[r].toLocaleLowerCase()) {
return false;
}
l++;
r--;
}
return true;
}
|
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 | impl Solution {
pub fn is_palindrome(s: String) -> bool {
let ss: Vec<char> = s.chars().collect();
let mut l = 0;
let mut r = ss.len() - 1;
while l < r {
while l < r && !(ss[l].is_alphabetic() || ss[l].is_numeric()) {
l += 1;
}
while l < r && !(ss[r].is_alphabetic() || ss[r].is_numeric()) {
r -= 1;
}
if ss[l].to_ascii_lowercase() != ss[r].to_ascii_lowercase() {
return false;
}
// 防止 usize 破界
if r == 0 {
return true;
}
l += 1;
r -= 1;
}
true
}
}
|