XTAO's Tech Blog
0%

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

发表于 更新于 分类于 评论数：
934 1 分钟

题目描述

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++ 函数可以记录一下，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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)

推荐文章