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