PJCHENder 未整理筆記

[演算法] Reverse Words

2017-09-26

[演算法] 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() 這個方法。
1
function reverseWords (str) {...}

演算法實做

字串反轉

比較重要的是如何不用 Array.prototype.reverse() 的方式來實做將字串反過來,我們可以觀察假設一個字串原本是 abcd,它的 index 會是 0123,如果反過來變成 dbca 的話,它的 index 會是 3210,寫成條列是我們就可以看出些有趣的規律:

1
2
3
4
abcd
0123
3210
dcba

可以發現 a+d=3, b+c = 3, c+b=3, d+a=3;利用這樣的規則,我們就可以把我們的字串反轉過來,例如:

1
2
3
4
5
6
let str = 'abcd';
let strReverse = '';
for (let i = str.length - 1; i >= 0; i--) {
strReverse += str[i];
}
console.log(strReverse); // dbca

不要整句反轉

為了不要整句反轉,所以我們要根據空行把句子拆開成陣列:

1
2
3
4
function reverseWords(str) {
strArr = str.split(' ');
/* ... */
}

接著要把陣列 strArr 中的每個元素進行字串反轉,這裡我們使用 Array.prototype.map() 這個方法,最後在透過 Array.prototype.join() 這個方法把它組回字串:

1
2
3
4
5
6
7
8
9
10
11
12
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(' ');
}

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

資料來源

掃描二維條碼,分享此文章