## 题目地址

https://leetcode.com/problems/valid-palindrome/

## 题目描述

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
`"A man, a plan, a canal: Panama"` is a palindrome.
`"race a car"` is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

## 思路

``````class Solution {
public:
bool isPalindrome(string s) {
int left = 0, right = s.size() - 1 ;
while (left < right) {
if (!isAlphaNum(s[left])) ++left;
else if (!isAlphaNum(s[right])) --right;
else if ((s[left] + 32 - 'a') %32 != (s[right] + 32 - 'a') % 32) return false;
else {
++left; --right;
}
}
return true;
}
bool isAlphaNum(char &ch) {
if (ch >= 'a' && ch <= 'z') return true;
if (ch >= 'A' && ch <= 'Z') return true;
if (ch >= '0' && ch <= '9') return true;
return false;
}
};
``````

``````class Solution {
public:
bool isPalindrome(string s) {
int left = 0, right = s.size() - 1 ;
while (left < right) {
if (!isalnum(s[left])) ++left;
else if (!isalnum(s[right])) --right;
else if ((s[left] + 32 - 'a') %32 != (s[right] + 32 - 'a') % 32) return false;
else {
++left; --right;
}
}
return true;
}
};
``````

### 思路2

• 如果两个指针的元素不相同，则直接返回false,
• 如果两个指针的元素相同，我们同时更新头尾指针，循环。 直到头尾指针相遇。

• 双指针

## 代码

• 语言支持：JS，C++，Python

JavaScript Code:

``````
/*
* @lc app=leetcode id=125 lang=javascript
*
* [125] Valid Palindrome
*/
// 只处理英文字符（题目忽略大小写，我们前面全部转化成了小写， 因此这里我们只判断小写）和数字
function isValid(c) {
const charCode = c.charCodeAt(0);
const isDigit =
charCode >= "0".charCodeAt(0) && charCode <= "9".charCodeAt(0);
const isChar = charCode >= "a".charCodeAt(0) && charCode <= "z".charCodeAt(0);

return isDigit || isChar;
}
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
s = s.toLowerCase();
let left = 0;
let right = s.length - 1;

while (left < right) {
if (!isValid(s[left])) {
left++;
continue;
}
if (!isValid(s[right])) {
right--;
continue;
}

if (s[left] === s[right]) {
left++;
right--;
} else {
break;
}
}

return right <= left;
};
``````

C++ Code:

``````class Solution {
public:
bool isPalindrome(string s) {
if (s.empty())
return true;
const char* s1 = s.c_str();
const char* e = s1 + s.length() - 1;
while (e > s1) {
if (!isalnum(*s1)) {++s1; continue;}
if (!isalnum(*e)) {--e; continue;}
if (tolower(*s1) != tolower(*e)) return false;
else {--e; ++s1;}
}
return true;
}
};
``````

Python Code:

``````class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
break
return right <= left

def isPalindrome2(self, s: str) -> bool:
"""
使用语言特性进行求解
"""
s = ''.join(i for i in s if i.isalnum()).lower()
return s == s[::-1]
``````

评论
0 评论