125 验证回文串

题目

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

题解

1. 先过滤字符串，然后使用双指针，依次进行对比。

TIP

执行用时：88 ms, 在所有 JavaScript 提交中击败了 79.2% 的用户
内存消耗：40.2 MB, 在所有 JavaScript 提交中击败了 60.81% 的用户

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    s = s.replace(/\W|_/gi, '').toLowerCase()
    let left = 0;
    let right = s.length -1

    while( left <=  right) {
        if(s[left] !== s[right]) return false
        left++
        right--
    }
    return true
};

• 时间复杂度： `O(n)`，使用 while循环
• 空间复杂度： `O(1)`，使用常数级别的空间
• 最好情况： 字符串较短，则对比次数较小。或者较早发现不是回文
• 最坏情况： 字符串较大，则需要进行多次对比。或者验证之后为正确字符

TIP

执行用时：76 ms, 在所有 JavaScript 提交中击败了 97.4% 的用户
内存消耗：41.1 MB, 在所有 JavaScript 提交中击败了 46.63% 的用户

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    s = s.replace(/\W|_/gi, '').toLowerCase()
    const {length: l} = s
    let first = s.slice(0, l/2)
    let last = s.slice(l/2+l%2)

    return first === last.split('').reverse().join('')
};

• 时间复杂度： `O(1)`，没有使用循环
• 空间复杂度： `O(n)`，使用变量来储存要比较的字符串
• 最好情况：
• 最坏情况：