Sunday, November 16, 2014

[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.
思路:
回文必定是左右对称。所以双指针left/right分别向中间扫描比较。遇到非数字字母的字符则跳过。直到left/right对应的数字字母不同,返回false;或left/right相遇,返回true。
corner case: 空字符串,或字符串中没有数字字母。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    bool isPalindrome(string s) {
        int left=0, right=s.size()-1;
        while(left<right) {
            while(left<s.size() && !isalnum(s[left])) left++;
            while(right>=0 && !isalnum(s[right])) right--;
            if(left>=right) return true;
            if(tolower(s[left++])!=tolower(s[right--])) return false;
        }
        return true;
    }
};

总结:
简单题,但实现仍需注意细节:
ln 6-7在寻找下一个有效字母数字时,必须要检查越界问题。不然如果整个s不含有字母数字,则会出错。
ln 8 要增加一个判断,同样是为了s不含有字母数字的情况。
ln 9 用了tolower库函数。并且一定要记得最后移动双指针。

1 comment:

  1. 用continue好像就不用检查越界问题了

    class Solution {
    public:
    bool isPalindrome(string s) {
    int i=0,j=int(s.length())-1;
    while(i='A' && s[i]<='Z') s[i]='a'+s[i]-'A';
    if(s[j]>='A' && s[j]<='Z') s[j]='a'+s[j]-'A';
    if(s[i++]!=s[j--]) return false;
    }
    return true;
    }
    };

    ReplyDelete