LeetCode Valid Palindrome

LeetCode 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.


本题要判断一个字符串是否是回文串,回文串的意思是从左往右读和从右往左读出来的字符串是一样的。本题在判断是否为回文时,只考虑数字和字母,并且忽略字母的大小写。

思路很简单,两个指针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。

One thought on “LeetCode Valid Palindrome

  1. Pingback: LeetCode Palindrome Linked List | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *