0%

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

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)