# LeetCode Problem: Valid Palindrome

By | 2013 年 1 月 19 日

To solving this problem, using two pointer to track the characters in the string. i, from the beginning of string; j, from the back of the string.

while i < j do {
1.if s[i] is not alphanumeric, moving i forward and continue
2.if s[j] is not alphanumeric, moving j backward and condinue
3.if s[i] != s[j] (ignoring the cases) return false.
4.moving i forward and j backward by one step
}
return true;

Valid Palindrome Jan 13
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.

Code, 60ms pass large set

class Solution {
inline bool isAlpha(char c) {
if(c >= 'a' && c <= 'z') return true;
if(c >= 'A' && c <= 'Z') return true;
if(c >= '0' && c <= '9') return true;
return false;
}
inline char lower(char c) {
if(c >= 'A' && c <= 'Z')
return ('a' + (c-'A'));
return c;
}
public:
bool isPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int i = 0, j = s.size() - 1;
while(i < j) {
if(!isAlpha(s[i])) {
++i;
continue;
}
if(!isAlpha(s[j])) {
--j;
continue;
}
if(lower(s[i++]) != lower(s[j--])) {
return false;
}
}
return true;
}
};

Code rewrite at 2013-2-4

class Solution {
bool isValidChar(char c) {
if (c >= '0' && c <= '9')
return true;
if (c >= 'a' && c <= 'z')
return true;
if (c >= 'A' && c <= 'Z') {
return true;
}
return false;
}
char lower(char c) {
if (c >= 'A' && c <= 'Z') {
return 'a' + c - 'A';
}
}
public:
bool isPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s.size() <= 1) return true;
int si=0,ei=s.size()-1;
while(si < ei) {
while(si < ei && !isValidChar(s[si]))
++si;
while(si < ei && !isValidChar(s[ei]))
--ei;
if(lower(s[si]) != lower(s[ei])) {
return false;
}
++si;--ei;
}
return true;
}
};

Code rewrite at 2013-03-03

class Solution {
bool isValid(char c) {
if (c >= '0' && c <= '9')
return true;
if (c >= 'a' && c <= 'z')
return true;
if (c >= 'A' && c <= 'Z') {
return true;
}
return false;
}
char lower(char c) {
if (c >= 'A' && c <= 'Z') {
return 'a' + c - 'A';
}
}
public:
bool isPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s.size() <= 1) return true;
int si=0,ei=s.size()-1;
while(si < ei) {
if(!isValid(s[si])) {
++si;
continue;
}
if(!isValid(s[ei])) {
--ei;
continue;
}
if(lower(s[si++]) != lower(s[ei--])) {
return false;
}
}
return true;
}
};

## 3 thoughts on “LeetCode Problem: Valid Palindrome”

1. zhangyuxiu

我认为第二种算法，isPalindrome函数的大while循环应该为：
while(si < ei) {
while(si < ei && !isValidChar(s[si]))
++si;
while(si < ei && !isValidChar(s[ei]))
–ei;
if (si == ei ) return true; //当s[si]为非字符数字时，其没有lower()值。
if(lower(s[si]) != lower(s[ei])) {
return false;
}
++si;–ei;
}

1. uniEagle Post author

刚才重写了一个，while里面还是用continue来处理比较好，不用写循环嵌套，那样会多几个si