[Leetcode]125. Valid Palindrome (C++)

题目描述

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.

例子

例子 1

Input: “A man, a plan, a canal: Panama” Output: true

例子 2

Input: “A man, a plan, a canal: Panama” Output: true

其他

s consists only of printable ASCII characters.

解题思路

这道题比较简单，通过前后两个指针从两侧遍历，遇到是字母/数字的进行比较即可，有几个比较好用的 C++ 函数可以记录一下，代码如下：

#include <string>
#include <locale>

class Solution {
public:
    bool isPalindrome(std::string s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !std::isalnum(s[left])) left++;
            while (right > left && !std::isalnum(s[right])) right--;

            if (left == right) break;

            if (std::isalpha(s[left]) && (std::toupper(s[left]) != std::toupper(s[right]))) return false;
            else if (std::isdigit(s[left]) && s[left] != s[right]) return false;
            left++;
            right--;
        }

        return true;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)