2017年9月21日 星期四

[演算法] Reverse Words: 把單字反過來寫

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

問題描述

在這次的練習中,我們要實做一個能夠將單字反轉過來的函式,但有兩點要注意的:
  1. 反轉的是單字,而不是整個句子,例如 This is a cat,應該要變成 sihT si a tac,而不是 tac a si sihT
  2. 不能使用 Array.prototype.reverse() 這個方法。
function reverseWords (str) {...}

演算法實做

字串反轉

比較重要的是如何不用 Array.prototype.reverse() 的方式來實做將字串反過來,我們可以觀察假設一個字串原本是 abcd,它的 index 會是 0123,如果反過來變成 dbca 的話,它的 index 會是 3210,寫成條列是我們就可以看出些有趣的規律:
abcd
0123
3210
dcba
可以發現 a+d=3, b+c = 3, c+b=3, d+a=3;利用這樣的規則,我們就可以把我們的字串反轉過來,例如:
let str = 'abcd'
let strReverse = ''
for (let i = str.length - 1; i >= 0 ; i--){
  strReverse += str[i]
}
console.log(strReverse) // dbca

不要整句反轉

為了不要整句反轉,所以我們要根據空行把句子拆開成陣列:
function reverseWords (str) {
  strArr = str.split(' ')
  /* ... */
}
接著要把陣列 strArr 中的每個元素進行字串反轉,這裡我們使用 Array.prototype.map() 這個方法,最後在透過 Array.prototype.join() 這個方法把它組回字串:
function reverseWords (str) {
  strArr = str.split(' ')

  strArrReverse = strArr.map(str => {
    let newStr = ''
    for (let i = str.length - 1; i >= 0; i--) {
      newStr += str[i]
    }
    return newStr
  })
  return strArrReverse.join(' ')
}

完整程式碼

function reverseWords (str) {
  strArr = str.split(' ')

  strArrReverse = strArr.map(str => {
    let newStr = ''
    for (let i = str.length - 1; i >= 0; i--) {
      newStr += str[i]
    }
    return newStr
  })
  return strArrReverse.join(' ')
}

reverseWords('This is a cat')                // sihT si a tac
reverseWords('This is a string of words')    // sihT si a gnirts fo sdrow
reverseWords('Coding JavaScript')            // gnidoC tpircSavaJ

資料來源

0 意見:

張貼留言