LeetCode 125 验证回文串 简单
题目 - 点击直达
- 1. 125 验证回文串 简单
- 1. 题目详情
- 1. 原题链接
- 2. 题目要求
- 3. 基础框架
- 2. 解题思路
- 1. 思路分析
- 2. 时间复杂度
- 3. 代码实现
1. 125 验证回文串 简单
1. 题目详情
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false 。
1. 原题链接
LeetCode 125 验证回文串 简单
2. 题目要求
示例 1:
输入: s = “A man, a plan, a canal: Panama”
输出:true
解释:“amanaplanacanalpanama” 是回文串。
示例 2:
输入:s = “race a car”
输出:false
解释:“raceacar” 不是回文串。
示例 3:
输入:s = " "
输出:true
解释:在移除非字母数字字符之后,s 是一个空字符串 “” 。
由于空字符串正着反着读都一样,所以是回文串。
提示:
1 <= s.length <= 2 * 105
s 仅由可打印的 ASCII 字符组成
3. 基础框架
● Cpp代码框架
class Solution {
public:
bool isPalindrome(string s) {
}
};
2. 解题思路
1. 思路分析
(
1
)
(1)
(1) 快排思想,借助两个变量
l
l
l和
r
r
r
(
2
)
(2)
(2)
l
l
l从字符串起始0下标位置向后找到第一个字母字符;
(
3
)
(3)
(3)
r
r
r从字符串最后一个字符size-1下标位置开始向前找到第一个字母字符;
(
4
)
(4)
(4) 对找到的两个字母字符分别进行判断,如果是大写字母则变为小写字母;
(
5
)
(5)
(5) 比较这两个字母字符,相等就
l
l
l和
r
r
r就继续分别查找下一个字母字符,直到
l
l
l和
r
r
r相遇说明所有须比较的字母字符都符合要求,结束并返回true;只有存在一对不相等的字母字符说明不是回文串,直接返回false;
2. 时间复杂度
O
(
N
)
O(N)
O(N)
l
l
l向后查找,
r
r
r向前查找,直到二者相遇时才结束查找,共查找了
n
n
n次;
3. 代码实现
class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = s.size() - 1;
while(l < r){
while(l < s.size() && !isalpha(s[l]) && !isdigit(s[l])){
l++;
}
while(r >= 0 && !isalpha(s[r]) && !isdigit(s[r])){
r--;
}
if(l < r){
if(isupper(s[l])) s[l] += 32;
if(isupper(s[r])) s[r] += 32;
if(s[l] != s[r]) return false;
l++;
r--;
}
}
return true;
}
};
T h e The The e n d end end