来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位脉友讲述了自己在国企的工作经历，211计算机硕士毕业，入职国企半年，相比入职大厂的同学，薪资低了一大截，每天很清闲，到点就下班，穷的很稳定，有点怀疑人生了。
评论区有在国企和私企都呆过的脉友认为国企适合做职业的终点，不适合做职业的起点。毕业去私企赚点钱，然后上岸国企应该是大部分人都期望的一条职业路线吧。还有人建议楼主把空闲的时间用来做副业。更多的人是羡慕楼主工作的轻松，而且认为这待遇也不低。我觉得如果楼主一毕业就选择了私企，工作一段时间后大概率也是会后悔当初没有选择国企。
不少同学对虎哥的视频非常认可，直接成为了原始粉。
言归正传，今天我们来分享一道高频面试题「验证回文串」。
题目描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
举个例子：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
思路解析
先明确回文串的概念：正着读和反着读都一样。换句话说就是对于字符串s，将s进行反转得到字符串s'，如果s == s'，那么s就是回文串。
本题中的字符串s包含一些非字母数字干扰字符，在判断的时候可以跳过干扰字符。
采用双指针法，定义两个变量left = 0，right = s.length() - 1。
当left < right，left向右移动，直到left指向字母或数字，right向左移动，直到right指向字母或数字。如果left >= right说明s是回文串，否则进入步骤2。
比较left和right指向字符对应的小写字符是否相等，如果不相等说明s不是回文串，否则left和right同时移动，++left，--right，进入步骤1。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
bool isPalindrome(string s) {
//定义两个索引
int left = 0, right = s.length() - 1;
while (left < right) {
//left需要指在字母或数字上
while (left < right && !isalnum(s[left])) {
++left;
}
//right需要指在字母或数字上
while (left < right && !isalnum(s[right])) {
--right;
}
if (tolower(s[left]) != tolower(s[right])) {
return false;
}
++left;
--right;
}
return true;
}
};
python代码
class Solution: def isPalindrome(self, s: str) -> bool: left, right = 0, len(s) - 1 while left < right: #left需要指在字母或数字上 while left < right and not s[left].isalnum(): left += 1 #right需要指在字母或数字上 while left < right and not s[right].isalnum(): right -= 1 if s[left].lower() != s[right].lower(): return False left += 1 right -= 1 return True
复杂度分析
时间复杂度： 只需要遍历一遍字符串，所以时间复杂度为O(n)，其中n为字符串的长度。
空间复杂度： 只使用了两个索引，所以空间复杂度为O(1)。
今天的分享就到这里，希望大家能有所收获！
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
