125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

---

本题要判断一个字符串是否是回文串，回文串的意思是从左往右读和从右往左读出来的字符串是一样的。本题在判断是否为回文时，只考虑数字和字母，并且忽略字母的大小写。 思路很简单，两个指针i,j，分别指向字符串的头尾，各自跳过所有非数字和字母的字符，然后把大写字母转换为小写字母，如果出现头尾字符不一样的情况，则不是回文，立即返回false。如果比完整个字符串都相等，则是回文，返回true。 完整代码如下：

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
    if (c >= ‘A’&& c <= ‘Z’)
        return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() – 1;
        while (i < s.size() && j >= 0) {
            while (!isAlphaNum(s[i]) && i < s.size())
                i++;
            if (i >= s.size())
                break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && j >= 0)
                j–;
            if (j < 0)
                break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)
                return false;
            i++;
            j–;
        }
        return true;
    }
};

本代码提交AC，用时12MS。

二刷。其实i,j不用走完全程，只需要走到他们交错之后就可以了，也就是只需要判断整个字符串的前半段和后半段是否逆序相等。
至于代码，其实就是把while循环和if条件判断改一下，如下：

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
    if (c >= ‘A’&& c <= ‘Z’)
        return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() – 1;
        while (i <= j) {
            while (!isAlphaNum(s[i]) && i <= j)
                i++;
            if (i > j)
                break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && i <= j)
                j–;
            if (i > j)
                break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)
                return false;
            i++;
            j–;
        }
        return true;
    }
};

本代码提交AC，用时9MS。

三刷。更简洁的代码：

class Solution {
public:
	bool IsValid(char c) {
		return (c >= '0'&&c <= '9') || (c >= 'a'&&c <= 'z');
	}
	bool isPalindrome(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return true;
		int i = 0, j = n - 1;
		while (i < j) {
			s[i] = tolower(s[i]);
			s[j] = tolower(s[j]);

			if (!IsValid(s[i]))++i;
			else if (!IsValid(s[j]))--j;
			else {
				if (s[i] != s[j])break;
				else {
					++i;
					--j;
				}
			}
		}
		return i >= j;
	}
};

本代码提交AC，用时16MS。