0125. 验证回文串

题目地址(125. 验证回文串)

题目描述

1
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
2
3
说明:本题中,我们将空字符串定义为有效的回文串。
4
5
示例 1:
6
7
输入: "A man, a plan, a canal: Panama"
8
输出: true
9
示例 2:
10
11
输入: "race a car"
12
输出: false
Copied!

前置知识

  • 回文
  • 双指针

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • facebook
  • microsoft
  • uber
  • zenefits

思路

这是一道考察回文的题目,而且是最简单的形式,即判断一个字符串是否是回文。
针对这个问题,我们可以使用头尾双指针,
  • 如果两个指针的元素不相同,则直接返回 false,
  • 如果两个指针的元素相同,我们同时更新头尾指针,循环。 直到头尾指针相遇。
时间复杂度为 O(n).
拿“noon”这样一个回文串来说,我们的判断过程是这样的:
125.valid-palindrome-1
拿“abaa”这样一个不是回文的字符串来说,我们的判断过程是这样的:
125.valid-palindrome-2

关键点解析

  • 双指针

代码

  • 语言支持:JS,C++,Python
JavaScript Code:
1
/*
2
* @lc app=leetcode id=125 lang=javascript
3
*
4
* [125] Valid Palindrome
5
*/
6
// 只处理英文字符(题目忽略大小写,我们前面全部转化成了小写, 因此这里我们只判断小写)和数字
7
function isValid(c) {
8
const charCode = c.charCodeAt(0);
9
const isDigit =
10
charCode >= "0".charCodeAt(0) && charCode <= "9".charCodeAt(0);
11
const isChar = charCode >= "a".charCodeAt(0) && charCode <= "z".charCodeAt(0);
12
13
return isDigit || isChar;
14
}
15
/**
16
* @param {string} s
17
* @return {boolean}
18
*/
19
var isPalindrome = function (s) {
20
s = s.toLowerCase();
21
let left = 0;
22
let right = s.length - 1;
23
24
while (left < right) {
25
if (!isValid(s[left])) {
26
left++;
27
continue;
28
}
29
if (!isValid(s[right])) {
30
right--;
31
continue;
32
}
33
34
if (s[left] === s[right]) {
35
left++;
36
right--;
37
} else {
38
break;
39
}
40
}
41
42
return right <= left;
43
};
Copied!
C++ Code:
1
class Solution {
2
public:
3
bool isPalindrome(string s) {
4
if (s.empty())
5
return true;
6
const char* s1 = s.c_str();
7
const char* e = s1 + s.length() - 1;
8
while (e > s1) {
9
if (!isalnum(*s1)) {++s1; continue;}
10
if (!isalnum(*e)) {--e; continue;}
11
if (tolower(*s1) != tolower(*e)) return false;
12
else {--e; ++s1;}
13
}
14
return true;
15
}
16
};
Copied!
Python Code:
1
class Solution:
2
def isPalindrome(self, s: str) -> bool:
3
left, right = 0, len(s) - 1
4
while left < right:
5
if not s[left].isalnum():
6
left += 1
7
continue
8
if not s[right].isalnum():
9
right -= 1
10
continue
11
if s[left].lower() == s[right].lower():
12
left += 1
13
right -= 1
14
else:
15
break
16
return right <= left
17
18
def isPalindrome2(self, s: str) -> bool:
19
"""
20
使用语言特性进行求解
21
"""
22
s = ''.join(i for i in s if i.isalnum()).lower()
23
return s == s[::-1]
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。