剑指 Offer II 018. 有效的回文

---

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20018.%20%E6%9C%89%E6%95%88%E7%9A%84%E5%9B%9E%E6%96%87/README.md

剑指 Offer II 018. 有效的回文

题目描述

给定一个字符串 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)$。

Python3

class Solution:def isPalindrome(self, s: str) -> bool:l,r=0,len(s)-1while l<r:while l<r and not s[l].isalnum():l+=1while l<r and not s[r].isalnum():r-=1if s[l].lower()!=s[r].lower():return Falsel,r=l+1,r-1 #[注意]return True

Java

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;}
}

C++

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;}
};

Go

func isPalindrome(s string) bool {i, j := 0, len(s)-1for 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'
}

TypeScript

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;
}

Rust

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}
}

Swift

class Solution {func isPalindrome(_ s: String) -> Bool {var i = s.startIndexvar j = s.index(before: s.endIndex)while i < j {while i < j && !s[i].isLetter && !s[i].isNumber {i = s.index(after: i)}while i < j && !s[j].isLetter && !s[j].isNumber {j = s.index(before: j)}if i >= j {break}if s[i].lowercased() != s[j].lowercased() {return false}i = s.index(after: i)j = s.index(before: j)}return true}
}