LeetCode: Valid Palindrome

Initial solution:
Toooooo slow, almost same like python...

O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: bool isPalindrome(string s) { int size=s.size(); for(int i=0; i<s.size(); i++){ if(s[i] >= 'a' && s[i] <= 'z') continue; if(s[i] >= 'A' && s[i] <= 'Z'){ s[i]=s[i]+'a'-'A'; continue; } if(s[i] >= '0' && s[i] <= '9') continue; s.erase(i--, 1); } int length = s.size(); for(int i=0; i < s.size()/2; i++){ if(s[i] != s[length-1-i]) return false; } return true; } };

Solution two,

Processing the string format and comparing char from left and right side of the string at the same time.
Codes are a little complex, but speed up a lot.

O(n)

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 27 28 29 30

class Solution { public: bool validate(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; } bool isPalindrome(string s) { int left=0; int right=s.size()-1; while(left<right){ while(!validate(s[left]) ) { left++; if(left >= right) break; } while(!validate(s[right])) { right--; if(right <= left) break; } if(left>=right) break; if(s[left] >= 'A' && s[left] <='Z') s[left]=s[left]+'a'-'A'; if(s[right] >= 'A' && s[right] <='Z') s[right]=s[right]+'a'-'A'; if(s[left] != s[right]) return false; left++; right--; } return true; } };

Solution three:
Modify solution two in two ways:
1. change the ugly while loop to if ... continue;
2. add two library function to simplify codes.
#include<cctype>    tolower()     isalnum()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: bool isPalindrome(string s) { int left=0; int right=s.size()-1; while(left<right){ if(!isalnum(s[left]) ) { left++; continue; } if(!isalnum(s[right])) { right--; continue; } if(tolower(s[left]) != tolower(s[right])) return false; left++; right--; } return true; } };

Reference: http://yucoding.blogspot.com/2013/05/leetcode-question-126-valid-palindrome.html