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.
判断是否是回文字符串。
解题思路：
刚拿到这个题啊，因为之前 递归反转栈 那道题的影响，我直接就上了递归了。即判断是否是回文字符串，先判断第一个和最后一个字符是否相同，如果相同，则取中间的串为子串进行递归。
递归返回条件是字符串只有一个字符或两个字符的时候。
于是我写了以下的代码：
class Solution { bool isPalin(string s) { if(s.size() == 1) return true; if(s.size() == 2) if(s[0] == s[1]) return true; else return false; if(s[0] == s.back()){ string sub = s.substr(1,s.size()-2); bool isSub = isPalindrome(sub); if(isSub) return true; } return false; } public: bool isPalindrome(string s) { if(s.size() == 0) return true; string str2; for(int i = 0;i < s.size();i++){ if(isalnum(s[i])) str2.append(1,tolower(s[i])); } if(str2.size() == 0) return true; return isPalin(str2); } };
提交上去以后……
超时！！
果然还是我想多了。。。
其实这一题特别简单，一个指针指向第一个，一个指针指向最后一个，遍历一遍就可以了。遇到非数字字母字符的忽略掉，如果两个字符不相等，就return false。
代码如下：
class Solution { public: bool isAlphanumeric(char &c){ if(c >= ‘A‘ && c <= ‘Z‘){ c = c | 0x20; return true; } else if( c >= ‘0‘ && c <= ‘9‘ || c >= ‘a‘ && c <= ‘z‘) return true; else return false; } bool isPalindrome(string s) { int i = 0; int j = s.size() - 1; while(i < j){ if(!isAlphanumeric(s[i])) ++i; else if(!isAlphanumeric(s[j])) --j; else if(s[i++] != s[j--]) return false; } return true; } };
【LeetCode练习题】Valid Palindrome,布布扣,bubuko.com
原文：http://www.cnblogs.com/4everlove/p/3669481.html