_Ghosteye验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回
true；否则，返回false。
示例 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 * 10^5s仅由可打印的 ASCII 字符组成
思路
将所有大写字符转换为小写字符、并移除所有非字母数字字符之后
反转字符串对比, 相等则是回文串.
双指针, 从字符串两端开始对比.
栈, 先进后出, 保存字符串前半部分与后半部分对比.
正则+反转字符串
时间
52ms击败100%, 内存46.3MB击败50.43%
TypeScript
function isPalindrome(s: string): boolean {
const str = s.toLocaleLowerCase().replace(/[^a-z0-9]/g, '');
const reversed = str.split('').reverse().join('');
return str === reversed;
};正则+双指针
官方题解是循环的时候单独判断每一个字符是否符合正则表达式, 符合并转换为小写字母在判断, 我觉得太麻烦了. 反正都是要用正则直接根据题目先处理成小写和字母数字的字符串在用双指针判断.
时间
76ms击败69.83%, 内存44.3MB击败79.31%
TypeScript
function isPalindrome(s: string): boolean {
const str = s.toLocaleLowerCase().replace(/[^a-z0-9]/g, '');
let left = 0;
let right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
};正则+栈
时间
60ms击败98.28%, 内存45.2MB击败63.79%
TypeScript
function isPalindrome(s: string): boolean {
const alphanumeric = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
const stack: string[] = [];
const half = Math.floor(alphanumeric.length / 2);
for (let i = 0; i < half; i++) {
stack.push(alphanumeric[i]);
}
for (let i = half + (alphanumeric.length % 2); i < alphanumeric.length; i++) {
if (stack.pop() !== alphanumeric[i]) {
return false;
}
}
return true;
}