跳至主要内容

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

資料來源​