[leetcode] Valid Palindrome


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.

tag: two-pointers, string

简单题,处理前先把字符串提纯一下–删掉非数字字母字符,并将大写字符转换成小写。

然后用双指针算法。

注意:我已经习惯用cpp解题。一开始用c时完全捉襟见肘。

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty()){
            return true;
        }
        s = refine(s);
        int l = s.size() - 1;
        int i = 0;
        while(i <= l){
            if(s[i] != s[l]){
                return false;
            }
            i++;
            l--;
        }
        return true;
    }
    string refine(string s){//delete non-alphanumeric characters and lower the letters
        string ns;
        for(int i = 0; i < s.size(); i++){
            char c = s[i];
            if(c >= '0' && c <= '9'){//number
                ns.push_back(c);
            }
            else if(c >= 'a' && c <= 'z'){//lowercase letter
                ns.push_back(c);
            }
            else if(c >= 'A' && c <= 'Z'){//uppercase letter
                ns.push_back(c - 'A' + 'a');
            }
        }
        return ns;
    }
};

 

Untitled

Leave a comment

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.