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.
从中间向两边找，分奇偶两种情况，时间复杂度为O(n^2)。有一种时间复杂度为O(n)的算法，有空学习一下。
1 class Solution { 2 public: 3 bool isPalindrome(string s) { 4 int count = 0; 5 for (int i = 0; i < s.length(); ++i) { 6 if (s[i] >= ‘A‘ && s[i] <= ‘Z‘) { 7 s[i-count] = s[i] - ‘A‘ + ‘a‘; 8 } else if (s[i] >= ‘a‘ && s[i] <= ‘z‘ || s[i] >= ‘0‘ && s[i] <= ‘9‘) { 9 s[i-count] = s[i]; 10 } else { 11 count++; 12 } 13 } 14 s.resize(s.length() - count); 15 int a = 0, b = s.length() - 1; 16 while (a < b) { 17 if (s[a] != s[b]) { 18 return false; 19 } 20 a++; b--; 21 } 22 return true; 23 } 24 };
[Leetcode] Valid Palindrome,布布扣,bubuko.com
原文：http://www.cnblogs.com/easonliu/p/3630611.html