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.
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:
inline bool isValidChar(char &c) {
if (c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
return true;
}
else {
return false;
}
}
inline bool isLetter(char &c) {
if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
return true;
}
else {
return false;
}
}
inline bool compare(char &c1, char &c2) {
if (c1 == c2 || isLetter(c1) && isLetter(c2) && abs(c1 - c2) == 32) {
return true;
}
else {
return false;
}
}
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) {
while (i < j && !isValidChar(s[i])) ++i;
while (i < j && !isValidChar(s[j])) --j;
if (i < j) {
if (!compare(s[i], s[j]))
return false;
}
++i;
--j;
}
return true;
}
};
No comments:
Post a Comment