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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

定义vector容器存储处理后的字符，再遍历容器判断是否满足回文。

class Solution {
public:
    bool isPalindrome(string s) {
        //回文字符串：正读和反读一样。
        //关键：对于非字母，数字符号的处理。
        if(s==" ") return true;
        vector<char> a;
        //剔除
        for(int i=0;i<s.length();i++){
            if((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')){
                a.push_back(s[i]);
            }
            if(s[i]>='A'&&s[i]<='Z'){
                a.push_back(s[i]-'A'+'a');
            }
        }
        //比较
        for(int i=0;i<a.size()/2;i++){
            if(a[i]!=a[a.size()-1-i]){
                return false;
            }
        }
        return true;
    }
};

思路二

双指针，遍历与处理字符串、比较三个操作同时进行。

利用stl函数处理非字母/数字的过滤和字母大小写转换。
isalnum(char c):
判断字符变量c是否为字母或数字，若是则返回非零，否则返回零。
tolower(char c):
把字母字符转换成小写,非字母字符不做出处理。

class Solution {
public:
    bool isPalindrome(string s) {
        // 双指针
        if(s.size() <= 1) return true;
        int i = 0, j = s.size() - 1;
        while(i < j){
            while(i < j && !isalnum(s[i])) // 排除所有非字母或数字的字符
                i++;
            while(i < j && !isalnum(s[j]))
                j--;
            if(tolower(s[i++]) != tolower(s[j--])) //统一转换成小写字母再比较
                return false;
        }
        return true;
    }
};