LeetCode《初级算法》字符串之验证回文串 -- JavaScript

语言: CN / TW / HK

题目

题目链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xne8id/

image.png

题解

首先分析题目,因为输入的是包含标点符号的字符串,所以整个算法可以分为两个部分: * 将字母和数字字符提取出来;(遍历过滤,正则过滤) * 判断过滤后的字符串是否为有效的回文串;(双指针,反转字符串后判断是否相等)

1、使用遍历过滤


```js /* * @param {string} s * @return {boolean} / var isPalindrome = function(s) {

let sArr = [];
let head = null,
    rear = null;

// 过滤字符串
for(let item of s) {

    if(item <= 'Z' && item >= 'A') {

        sArr.push( String.fromCharCode(item.charCodeAt() + 'a'.charCodeAt() - 'A'.charCodeAt()))
    }else if( (item <= '9'  && item >= '0') || (item <= 'z' && item >= 'a')) {

        sArr.push(item);
    }

}

// 判断是否为回文串
head = 0;
rear = sArr.length - 1;
while(head < rear) {

    if(sArr[head] === sArr[rear]) {
        head++;
        rear--;
    }else {
        return false;
    }
}
return true;

};

```

2、改为使用正则过滤


首先复习一下 JavaScript 的正则的使用:

  1. 创建一个正则表达式

    • 使用正则表达式字面量;

      javascript var re = /ab+c/; let re = /a/; // 只匹配出现的第一个 a; let re = /a/g; // 匹配全部的a

    • 使用RegExp对象的构造函数创建一个正则表达式;

      js const re = new RegExp('a',g); const re = new RegExp(/[A-Z]/,i);

  2. 字符串的可以使用正则表达式的方法

    • str.match(regxp)

      传入一个 正则表达式对象 regxp,找到则返回字符串 str 中满足正则的字符数组;没找到则返回 null ;

      注:

      • 如果传入的参数不是正则表达式对象,则会被隐式转换成正则表达式对象;
      • 如果给的正则表达式中没有 g 标志,将只返回第一个匹配到的完整匹配,并一起返回其相关的捕获组
      • 如果没有传入正则对象,则返回 [""] 和其捕获组;
    • str.matchAll(regxp)

      传入一个正则表达式对象,返回一个包含所有结果(匹配+捕获组)迭代器;

      eg:

      js let str = 'test1test2'; const re = /test(\d)/g; // 使用 ​ console.log(str.matchAll(re)); // Object{} console.log(...str.matchAll(re)); // Array ["test1", "e", "st1", "1"] Array ["test2", "e", "st2", "2"]

      注:

      • 传入的正则表达式必须有 /g 标志;
    • str.replace()

      语法:

      js stringObject.replace(pattern,replacement)

      replace() 方法返回一个由替换值(replacement)替换 部分或所有的模式(pattern)匹配项后的新字符串。

      • 模式(pattern)可以是一个字符串或者一个正则表达式

      • 替换值(replacement)可以是 一个字符串 或者 一个每次匹配都要调用的回调函数。

      • 如果pattern是字符串,则仅替换第一个匹配项。

      • 如果 replacement 是字符串,则字符串中可以使用一些特殊变量名;

      • 如果 replacement 是回调函数,则

        javascript function(match,offset,string) { // match 代表匹配的子串 // string 代表被匹配的字符串 // offset 代表 match 在 string 中的开始索引 }

        并且函数返回值作为替换字符串;

      • 原字符串不会改变,只是返回一个经过改变的新字符串;

    • str.search(regexp)

      传入一个正则表达式对象,如果匹配成功则返回正则在字符串中首次匹配项的索引,否则返回 -1;


使用正则过滤代码如下:

```js /* * @param {string} s * @return {boolean} / var isPalindrome = function(s) {

let sArr = null;
let str = null;
let head = null,
    rear = null;

// 使用正则筛选
const re1 = /[A-Z]/g;
const re2 = /[a-z0-9]/g;

str = s.replace(re1,function(match) {

    return String.fromCharCode( match.charCodeAt() + 'a'.charCodeAt() - 'A'.charCodeAt());
}) // 将大写字母换成小写

sArr = str.match(re2); // 匹配所有字母和数字字符,注当字符串中没有匹配项时返回 null


if(sArr === null) {
    return true;
}


// 判断是否为回文串
head = 0;
rear = sArr.length - 1;
while(head < rear) {

    if(sArr[head] === sArr[rear]) {
        head++;
        rear--;
    }else {
        return false;
    }
}
return true;

}; ```


3、直接在传入的字符串上面使用首尾下标向中间遍历

这种方法没有预先对字符串进行处理,直接使用首尾下标一次遍历字符串,遍历时有如下规则: * 当首尾下标遇到非数字或非字母字符时,向中间推进一个位置; * 当首尾下标对应的字符相同(不区分大小写)时,首尾下标向中间推进一个位置,否则返回 false; * 直到首尾下标相等或尾下标小于首下标时结束遍历,并返回 true;

```js /* * @param {string} s * @return {boolean} / var isPalindrome = function(s) {

let head = 0,
    rear = s.length - 1;


// 判断是否为回文串
while(head < rear) {

    // 跳过非字母和非数字字符
    while(head < rear && s[head].search(/[a-z0-9]/i) === -1) {
        head++;
    }
    while(head < rear && s[rear].search(/[a-z0-9]/i) === -1) {
        rear--;
    }

    // 比较 s[head] 和 s[rear]
    if(head < rear ){
        let headItem = s[head],
            rearItem = s[rear];
        if(headItem >= 'A' && headItem <= 'Z') {
            headItem = String.fromCharCode( headItem.charCodeAt() + 'a'.charCodeAt() - 'A'.charCodeAt());
        }
        if(rearItem >= 'A' && rearItem <= 'Z') {
            rearItem = String.fromCharCode( rearItem.charCodeAt() + 'a'.charCodeAt() - 'A'.charCodeAt());
        }


        if(headItem === rearItem) {
            head++;
            rear--;
        }else {
            return false;
        }
    }else {
        return true;
    }

}
return true;

}; ```


大家如果有更好的思路和解法,欢迎大家一起来讨论啊~

这是使用 JavaScript 对 LeetCode《初级算法》的每道题的总结和实现的其中一篇,汇总篇在这里:

https://juejin.cn/post/7006692002125316103