翻轉字元串 (Reverse a String)

原文鏈接：FreeCodeCamp 初級演算法題 - 翻轉字元串

題目鏈接

• 中文鏈接

• 英文鏈接

• 級別：初級 (Basic Algorithm Scripting)

問題解釋

• 這個 function 接收一個字元串參數，返回翻轉後的字元串

• 比如接收的是 "hello"，那麼輸出就是 "olleh"

基本解法

思路提示

1. 先把字元串分割成為數組

2. 翻轉數組

3. 把翻轉後的數組合併為字元串

參考鏈接

• String.prototype.split

• Array.prototype.reverse

• Array.prototype.join

代碼

function reverseString(str) { var strArr = str.split(""); var reversedArr = strArr.reverse(); return reversedArr.join("");}

解釋

• 第一步就是把傳入的 str 分割，並賦值給 strArr

• 第二步是把數組翻轉，並賦值給 reversedArr

• 第三步是返回合併之後的字元

• 需要注意的是，以上的 split 和 join 都不會改變原來的字元串或數組，但 reverse 會改變原來的數組

優化

代碼

function reverseString(str) { return str.split("").reverse().join("");}

解釋

• split 返回分割後的數組，因此可以直接調用 reverse

• reverse 方法返回的是翻轉後的數組，因此可以直接調用 join

• join 之後就是我們想要的字元串，直接返回即可

• 這裡用到了 Method Chaining，也就是方法的鏈式調用。只要你熟悉方法的返回值，就可以這麼做，好處在於可以不用創建這麼多變數

中級解法

思路提示

• 直接利用字元串方法，而不需要轉換成數組

• 多說一句，獲取字元串中 str 的某一個字元有兩種方式，分別是 str.charAt(i) 和 str[i]。兩種方式都只是讀取，均不可以通過賦值修改原字元串

代碼

function reverseString(str) { var result = ""; for (var i = str.length - 1; i >= 0; i--) { result += str[i]; } return result;}

解釋

• 首先我們先創建一個變數，叫 result，用於保存輸出結果

• 然後，從右邊開始遍歷字元串。值得注意的是，就像數組一樣，字元串一樣可以通過所以來獲取某一個字元。比如，str[0] 就是獲取第一個字元。再比如，str[-1] 就是獲取最後一個字元

• 因為是從右邊開始遍歷，那我們把每次遍歷到的字元直接加到 result 就可以了

• 需要注意的是邊界條件的確定，因為字元串的索引同樣是從 0 開始的，因此遍歷的初始值要設置為 str.length - 1，結束值為 0

高級解法

思路提示

• 通過字元串方法以及遞歸來翻轉

代碼

function reverseString(str) { // 設置遞歸終點(彈出條件) if (str.length === 1) { return str; } else { // 遞歸調用 return reverseString(str.substr(1)) + str[0]; }}

解釋

• 這種方法，一開始不能理解沒關係。等做到高級演算法題，再回來看看應該就可以理解了

• 遞歸涉及到兩個因素，遞歸調用以及彈出過程。reverseString(str.substr(1)) 就是遞歸調用，+ str[0] 就是彈出過程

• 代碼在執行到 reverseString(str.substr(1)) 的時候，會重新調用 reverseString，並傳入 str.substr(1) 作為參數。後面的 + str[0] 暫時不會執行

• 直到傳入的字元串長度為 1，就不會再去調用 reverseString 了，而是會執行 if 裡面的部分，返回當前傳入的 str。然後就會一步一步地執行之前的 + str[0]，也就是彈出過程

舉個例子：

var str = "abc";reverseString(str)

• 執行過程如下：

• 首先執行 reverseString("abc")，這時候傳入的 str 長度不為 1，所以執行 else 部分，也就是 reverseString(str.substr(1))。這就是遞歸調用，執行這段代碼，其中 str.substr(1) 為 "bc"
• reverseString("bc")，這時候傳入的 str 長度依舊不為 1，所以執行 reverseString(str.substr(1))，其中 str.substr(1) 為 "c"
• reverseString("c")，這時候傳入的 str 長度為 1，所以執行 if 中的部分，返回傳入的 str，也就是返回 "c"
• 回到 reverseString("bc") 這一步，此時的 str[0] 為 "b"。由於上一步的返回值是 "c"，那麼這一步的返回值是 "cb"

• 回到 reverseString("abc")，此時的 str[0] 為 "a"。由於上一步的返回值是 "cb"，那麼這一步的返回值是 "cba"

至此，我們得到了最終結果，"cba"

性能測試

• 鏈接

• 根據測試結果來看，第三種方法是最快的，第四種方法是最慢的

推薦閱讀：