2017年9月19日 星期二

[演算法] 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

資料來源

0 意見:

張貼留言