125.验证回文串
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释:"amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释:"raceacar" 不是回文串
提示:
1 <= s.length <= 2 * 105 字符串 s 由 ASCII 字符组成
解法
1、正则表达式 + 字符串反转
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function (s) {
const str = s.replaceAll(/[^A-Za-z0-9]/g, "").toLocaleLowerCase();
const cache = str.split("").reverse().join("");
return str === cache;
};
2、双指针
- 一个左指针,一个右指针,
- 遇到非字母和数字就跳过,遇到字母就进行比对
- 如果最后没有不想等的代表是回文字符串
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function (s) {
let left = 0;
let right = s.length - 1;
const reg = /[a-zA-Z0-9]/;
while (left < right) {
if (!reg.test(s[left])) {
left++;
} else if (!reg.test(s[right])) {
right--;
} else {
if (s[left].toLocaleLowerCase() !== s[right].toLocaleLowerCase()) {
return false;
}
left++;
right--;
}
}
return true;
};
3、递归实现
玩出花样的方式
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function (s) {
const reg = /[a-zA-Z0-9]/;
const isPalindromeHelper = function (s, left, right) {
if (left >= right) {
return true;
}
while (left < right && !reg.test(s[left])) {
left++;
}
while (left < right && !reg.test(s[right])) {
right--;
}
return (
s[left].toLocaleLowerCase() === s[right].toLocaleLowerCase() &&
isPalindromeHelper(s, ++left, --right)
);
};
return isPalindromeHelper(s, 0, s.length - 1);
};