125. Valid Palindrome

  • 25.7%

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

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

1
2
3
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.


isalnum 是否数字字符

isalpha 是否字母字符

tolower/toupper

方法一:

Here’s a clean C++ solution

1
2
3
4
5
6
7
8
9
bool isPalindrome(string s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) { // Move 2 pointers from each end until they collide
while (isalnum(s[i]) == false && i < j) i++; // Increment left pointer if not alphanumeric
while (isalnum(s[j]) == false && i < j) j--; // Decrement right pointer if no alphanumeric
if (toupper(s[i]) != toupper(s[j])) return false; // Exit and return error if not match
}

return true;
}

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
bool isPalindrome(string s) {
int n = s.size();
if(n==0) return true;
int i = 0, j = n-1;
while(i<j){
while(i<j && !isalnum(s[i])) i++;
while(i<j && !isalnum(s[j])) j--;
if(toupper(s[i])!=toupper(s[j])) return false;
i++; j--;
}
return true;
}
};

https://discuss.leetcode.com/topic/5581/here-s-a-clean-c-solution

Here’s a clean C++ solution

1
2
3
4
5
6
7
8
9
bool isPalindrome(string s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) { // Move 2 pointers from each end until they collide
while (isalnum(s[i]) == false && i < j) i++; // Increment left pointer if not alphanumeric
while (isalnum(s[j]) == false && i < j) j--; // Decrement right pointer if no alphanumeric
if (toupper(s[i]) != toupper(s[j])) return false; // Exit and return error if not match
}

return true;
}

https://discuss.leetcode.com/topic/10862/passed-clean-c-code

Passed clean c++ code

1
2
3
4
5
6
7
8
9
10
11
bool isPalindrome(string s) {
int start=0, end=s.length()-1;
while(start<end) {
if (!isalnum(s[start])) start++;
else if (!isalnum(s[end])) end--;
else {
if (tolower(s[start++])!=tolower(s[end--])) return false;
}
}
return true;
}

https://discuss.leetcode.com/topic/22479/python-in-place-two-pointer-solution

Python in-place two-pointer solution.

1
2
3
4
5
6
7
8
9
10
11
def isPalindrome(self, s):
l, r = 0, len(s)-1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l <r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l +=1; r -= 1
return True

80ms, 78.34%, April.23rd, 2016

https://leetcode.com/discuss/11241/challenge-shortest-possible-answer-python-palindrome-python

1
2
3
4
5
6
7
8
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
newS = [i.lower() for i in s if i.isalnum()]
return newS == newS[::-1]

https://discuss.leetcode.com/topic/8282/accepted-pretty-java-solution-271ms

Accepted pretty Java solution(271ms)

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
public class Solution {
public boolean isPalindrome(String s) {
if (s.isEmpty()) {
return true;
}
int head = 0, tail = s.length() - 1;
char cHead, cTail;
while(head <= tail) {
cHead = s.charAt(head);
cTail = s.charAt(tail);
if (!Character.isLetterOrDigit(cHead)) {
head++;
} else if(!Character.isLetterOrDigit(cTail)) {
tail--;
} else {
if (Character.toLowerCase(cHead) != Character.toLowerCase(cTail)) {
return false;
}
head++;
tail--;
}
}

return true;
}
}

Solution 2:

12ms, 40.64%, April.23rd, 2016

https://leetcode.com/discuss/80399/7-lines-concise-and-easy-understand-c-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool isPalindrome(string s) {
int l=0, r = s.size() - 1;
while(l <= r){
while(!isalnum(s[l]) && l < r) l++;
while(!isalnum(s[r]) && l < r) r--;
if(toupper(s[l]) != toupper(s[r])) return false;
l++, r--;
}
return true;
}
};

Solution 3:

16ms, 10.11%, April.23rd, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool isPalindrome(string s) {
transform(s.begin(), s.end(), s.begin(), ::tolower);
auto left = s.begin(), right = s.end();
while(left < right){
if(!::isalnum(*left)) ++left;
else if(!::isalnum(*right)) --right;
else if(*left != *right) return false;
else{left++, right--;}
}
return true;
}
};
谢谢你,可爱的朋友。