跳至主要内容

[演算法] Is Palindrome

此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

問題描述​

在忽略單字大小寫和標點符號的情況下，判斷字串是不是迴文（palindrome），也就是順著寫和逆著寫都是一樣的，例如，Madam, I'm Adam, race car。

function isPalindrome(str) {
  // return true or false
}
isPalindrome("Madam, I'm Adam"); // true

演算法實做​

步驟一：將所有的單字轉成小寫，拆成陣列，並且排除非英文單字​

我們先透過 String.toLowerCase() 將字串的內容全部轉成小寫，接著透過 String.split() 將字串拆成陣列，最後透過 Array.filter() 搭配一些正規表達式 /[a-z]/ 只保留小寫的英文字母，其他都過濾掉：

function isPalindrome(str) {
  // 將所有的單字轉成小寫，拆成陣列，並且排除非英文單字
  str = str.toLowerCase();
  charactersArr = str.split('').filter((character) => {
    return /[a-z]/.test(character);
  });

  /* ... */
}
步驟二：如果正著寫和逆著寫都一樣，則回傳 true，否則 false​

透過 Array.join() 將原本的陣列重新合併為字串。利用 Array.reverse() 將陣列反轉（[a, b, c] --> [c, b, a])：

function isPalindrome(str) {
  // 將所有的單字轉成小寫，拆成陣列，並且排除非英文單字
  /* ... */

  // 如果正著寫和反轉過來寫的內容都一樣，則回傳 true，否則 false
  return charactersArr.join('') === charactersArr.reverse().join('');
}

完整程式碼​

function isPalindrome (str) {
  // 將所有的單字轉成小寫，拆成陣列，並且排除非英文單字
  str = str.toLowerCase()
  charactersArr = str.split('').filter(character => {
    return /[a-z]/.test(character)
  })

  // 如果正著寫和反轉過來寫的內容都一樣，則回傳 true，否則 false
  return charactersArr.join('') === charactersArr.reverse().join('')
}

console.log(isPalindrome("Madam, I'm Adam"))    // true
console.log(isPalindrome("Hello, I'm Adam"))    // false

資料來源​