首页 > 代码库 > Valid Palindrome

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.

思路:使用start和end同时向后和向前移动,若s[start](或者s[end])不是数字或者字母,则继续将其向前(或者向后)移动。若某处s[start]和s[end]都是数字或者字母,且s[start]!=s[end],则返回false。

 1 class Solution { 2 public: 3     bool isPalindrome( string s ) { 4         int start = 0, end = (int)s.length()-1; 5         transform( s.begin(), s.end(), s.begin(), (int(*)(int))tolower ); 6         while( start < end ) { 7             while( start < end && !isAlphaNumerics( s[start] ) ) { ++start; } 8             while( start < end && !isAlphaNumerics( s[end] ) ) { --end; } 9             if( start < end && s[start] != s[end] ) { return false; }10             ++start; --end;11         }12         return true;13     }14 private:15     inline bool isAlphaNumerics( char achar ) {16         return ( achar >= a && achar <= z ) || ( achar >= 0 && achar <= 9 );17     }18 };