乐趣区

关于算法:力扣之有效的回文

jiezi

题目形容

给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。

阐明： 本题中，咱们将空字符串定义为无效的回文串。

示例 1:

输出: "A man, a plan, a canal: Panama"
输入: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输出: "race a car"
输入: false
解释："raceacar" 不是回文串

力扣原题目地址：https://leetcode.cn/problems/…

解决方案

计划一 判断第 i 项和第 j 项是否相等(i+j==s.length-1)

下方代码中，我就不辨别 i 和j了，间接是 i 和(filterS.length - 1) - i

var isPalindrome = function (s) {
    let flag = true
    // 先加工数据，替换去掉空格特殊符号，以及转成小写英文对立比照
    let filterS = s.replace(/[^A-Za-z0-9]/g, '').toLocaleLowerCase()
    for (let i = 0; i < filterS.length; i++) {
        // 如果有其中一项不合乎规定，就间接完结循环，返回后果即可
        if (filterS[i] != filterS[filterS.length - 1 - i]) {
            flag = false
            return flag
        }
    }
    // 最初再返回一下，因为有可能就是回文数，要返回 true
    return flag
};

留神，代码中的循环，其实不必循环所有项，只须要循环一半就行了，所以上述代码也能够换一下写法：
for (let i = 0; i < Math.trunc(filterS.length / 2); i++) {......}

留神冷门 api 之 Math.trunc()是取整的意思

  • Math.trunc(2.5) // 2
  • Math.trunc(3) // 3

应用 Math.trunc() 只循环一半尽管耗费内存少了一些，然而所破费的工夫会多一些了，因为 Math 公式 也会破费工夫的

计划二 字符串转数组反转比照

var isPalindrome = function (s) {
    // 先加工数据，去掉空格特殊符号，以及转成小写英文对立比照
    let filterS = s.replace(/[^A-Za-z0-9]/g, '').toLocaleLowerCase()
    let filterSArr = filterS.split('') // 转成失常程序数组
    let filterSArrReverse = filterS.split('').reverse() // 转成顺叙程序数组
    if (JSON.stringify(filterSArr) == JSON.stringify(filterSArrReverse)) { // 比拟是否相等
        return true
    } else {return false}
};

这办法尽管也能实现，然而性能却是没有计划一好，因为 数组的办法反转 、以及JSON 序列化 自身也是要消耗工夫的

总结

失常状况下，咱们应用空间换工夫，多消耗一点点内存，然而工夫提速一些，还是划算的。所以计划一是首选

另附正则，只能输出中英文数字 str = str.replace(/[^\u4E00-\u9FA5A-Za-z0-9]/g, '')

退出移动版