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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最近更新 1yr ago