写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【双指针】【回文串】【字符串】
题目来源
125. 验证回文串
题目解读
给你一个字符串 s
,该字符串包含的字符由 ASCII 字符组成。如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。请判断字符串 s
是否是回文串。
解题思路
对于本题可以有两种处理方法,一是先将字符换 s
中的字母字符筛选出来并将存储小写形式到临时变量 str
中,再对 str
进行回文串判断;而是直接对字符串 s
进行原地判断。
方法一:筛选+判断
对于筛选,别无二法,进行一次遍历,对遍历到的字符判断是否是字母或者数字,如果是,则将小写形式存放入 str
中。
判断回文有两种方法,一种是借助 API 对字符串逆序,将得到的逆序字符串与原字符串进行比较,如果相等,则说明字符串 str
是回文串;否则,不是回文串。
筛选+逆序判断回文
class Solution {
public:
bool isPalindrome(string s) {
string str;
for (char ch: s) {
if (isalnum(ch)) {
str+= tolower(ch);
}
}
string str_rev(str.rbegin(), str.rend());
return str== str_rev;
}
};
第二种是利用双指针进行迭代比较判断回文。具体地,使用相向双指针 i
、j
进行判断,两指针初始化分别指向字符串首和字符串尾,随后比较两指针指向的字符是否一致,一致就我们就相向地移动双指针,每移动一次,都需要进行一次比较,如果字符不一致则提前退出迭代比较过程表明字符串 str
并非回文串。
筛选+双指针判断回文
class Solution {
public:
bool isPalindrome(string s) {
string str;
for (char ch: s) {
if (isalnum(ch)) {
str+= tolower(ch);
}
}
int n = str.size();
int left = 0, right = n - 1;
while (left < right) {
if (str[left] != str[right]) {
return false;
}
++left;
--right;
}
return true;
}
};
复杂度分析
时间复杂度:
O
(
n
)
O(n)
O(n),
n
n
n 为字符串 s
的长度,我们筛选出字符串 str
的时间复杂度为
O
(
n
)
O(n)
O(n)。判断字符串 str
是否回文的时间复杂度为 str.size() / 2
,字符串 str
最长与字符串 s
长度一致,因此判断回文的时间复杂度为
O
(
n
/
2
)
O(n / 2)
O(n/2)。综合来看,筛选+判断的时间复杂度为
O
(
n
)
O(n)
O(n)。
空间复杂度: O ( n ) O(n) O(n),需要使用额外的空间来存放筛选后的字符,筛选后得到的字符串在最坏情况下,与原字符串一样长,因此,筛选+判断的空间复杂度为 O ( n ) O(n) O(n)
方法二:原地判断
我们可以直接在字符串 s
上使用双指针来判断回文。在比较字符是否相同之前需要先更新指针的指向,指针指向了数字或者字母字符时才进行字符相等性比较。
如果在比较中,遇到了字符不相等的情况,直接返回 false
;如果直到两指针相遇都没有返回,则最后返回 true
。
实现代码
class Solution {
public:
bool isPalindrome(string s) {
int n = s.size();
int left = 0, right = n - 1;
while (left < right) {
while (left < right && !isalnum(s[left])) {
++left;
}
while (left < right && !isalnum(s[right])) {
--right;
}
if (left < right) {
if (tolower(s[left]) != tolower(s[right])) {
return false;
}
++left;
--right;
}
}
return true;
}
};
复杂度分析
时间复杂度:
O
(
n
)
O(n)
O(n),
n
n
n 为字符串 s
的长度。
空间复杂度: O ( 1 ) O(1) O(1),仅使用了几个额外的变量。
知识回顾
回文串
回文串指的是正着读和反着读都是相同的字符串。常见的判断字符串是否回文有两种方法:
- 逆序判断:如果某个字符串逆序后的字符串与原字符串相等,那么该字符串是回文的。
- 双指针判断:迭代比较左、右指针指向的字符,字符相等则相向移动双指针直至两指针指向的字符不等返回
false
,或者两指针相遇退出迭代比较,返回true
。
回文串相关的题目:
- 判断字符串是否回文;
- 判断数字是否回文;
- 判断链表是否回文。
双指针
双指针,指的是在遍历元素的过程中,不是使用单个指针进行访问,而是使用两个指针来访问以达到某种目的。双指针的题目有:
- 两数之和;
- 计算链表的中间节点。
字符串操作
字符串操作的本质是对字符进行操作,在进行相应操作之前可以通过以下 C++ API \texttt{C++ API} C++ API 对字符进行判断以及进一步的操作。
C++代码 | 说明 |
---|---|
isalpha() | 判断字符是否是字母 |
isdigit() | 判断字符是否是数字 |
isalnum() | 判断字符是否是字母或者是数字(十进制) |
tolower() | 输出字母的小写形式 |
toupper() | 输出字母的大写形式 |
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。文章来源:https://www.toymoban.com/news/detail-708734.html
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。文章来源地址https://www.toymoban.com/news/detail-708734.html
到了这里,关于【面试经典150 | 双指针】验证回文串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!