今天在 Hackerrank 的安排是複習的一天，本來的題目是比較容易，所以在這裡我想我們就來做一些比較經典的問題，但又跟先前的主題有關係。這裡我選了一個經典的題目 “反轉字串”，其中 Scala 提供了四種解法，Python 五種，Golang 一種，Rust 兩種，那就讓我們開始吧！

Scala

在 Scala 的部分我列了四種解法，現在讓我們來看看。

object Solution {
    def main(args: Array[String]) {

        val s = "This is a challenge"

        def reverse1(s: String): String = s.reverse

        def reverse2(s: String): String = {
            s match {
                case "" => ""
                case _ => reverse2(s.tail) + s.head

            }
        }

        def reverse3(s: String): String = s.foldLeft("")((acc, c) => c + acc)

        def reverse4(s: String): String = (for(i <- s.length - 1 to 0 by -1) yield s(i)).mkString

        println(reverse1(s))
        println(reverse2(s))
        println(reverse3(s))
        println(reverse4(s))

    }
}

• reverse1 是最常用的解法，也就是直接 call String 的 method reverse 就可以囉！如果你去看 reverse 的 source code，會發現裡頭會用 while 的想法來去實作。
• reverse2 是用遞迴的概念來解。每次 s 進來，會先比對 s是不是空字串，如果是的話，也回傳空字串。假設不是的話，就回傳 reverse2(s.tail) + s.head ，這裡 s.tail 是字串除了第一個字的部分，例如 s 是 abc ，那麼 s.tail 就是 bc ，而 s.head 是 a 。reverse2(s.tail) + s.head 概念上就是每次把首字取出放到最後面，並且遞迴地完成。舉個例子來跑這個 Function，假如 s 是 cat 那麼一路執行下來會是 reverse2("at") + "c” => reverse2("t") + "a" + "c" => reverse2("") + "t" + "a" + "c" => "" + "t" + "a" + "c" => "tac" 。這裡順道提到，假如你去看 source code (scala.predef)，你會發現 String 其實是 java.lang.String 的 alias ( type String = java.lang.String )，並沒有 tail 和 head 這些 Method，今天可以對 String 調用這些 Method 是因為在 Scala 有一個叫做 implicit conversion 的機制。如果我們要讓 String 去調用 tail，那麼必須要有一個 Type 有 tail這個 Method，而且 Scope 內有一個 implicit function (想像是個隱藏在背後伺機而動的 function)，可以把 String 轉換成該 Type，那 String 就可以調用 tail囉！這裡實際上是會有個 implicit function 把 String 轉成 StringOps，可以參考這裡，就會看到 tail 和 head 了。
• reverse3 是運用另一個 Method foldLeft(跟 tail 和 head一樣，其實也是 StringOps 的 Method) 。 foldLeft也是 Functional 常見的做法。我們可以看到 foldLeft 執行時有兩個括號，這是 Scala 中的 Currying，概念上是這個 Function 可以只給部分的參數，變成另一個 Function，而之後使用時，只要再給剩下的參數。回到 foldLeft這邊第一個括號內是 "" ，是初始值的概念，也是第二個括號內 acc 一開始的值。第二個括號內 acc 意義上是 accumulator，會不斷地和 c 去做計算後再跟下一個 c做計算，直到沒有下個 c 為止。 c就是 String 照順序每次取的一個 Char。所以這裡關鍵是 c + acc 也就是把首字拿出來後，每次都放在右邊被串接。以剛才 cat 的例子，你會看到 "c" + "" => "a" + "c" => "t" + "ac" => "tac" 。可以思考一下為什麼叫 foldLeft (剛才說的概念像不像把一張紙一直往左折呢)
• reverse4 是運用了 for … yield， for(i <- s.length — 1 to 0 by -1)yield s(i) 可以想成就是 i 從 s.length — 1 開始一直到 0，每次遞增 -1 也就是遞減 1 ，所以以 cat 為例， i 會從 2 到 0，而每次都會產生 s(i) ，也就是 s(2) -> s(1) -> s(0) ，最後就會產生像是 [s(2) , s(1) , s(0) ]的 Sequence (實際上其實是 IndexedSeq)，最後把 for(i <- s.length — 1 to 0 by -1)yield s(i) 的結果用 mkString 變成 String 就完成了！

Python 3

在 Python 我列了五種解法，來看看吧！

def reverse1(s):
  return s[::-1]

def reverse2(s):
  r = ''
  for c in s:
    r = c + r
  return r

def reverse3(s):
  r = list(s)
  r.reverse()
  return ''.join(r)

def reverse4(s):
    s1 = ''.join(reversed(s))
    return s1

def reverse5(s):
    s1 = ''
    length = len(s) - 1
    while length >= 0:
        s1 = s1 + s[length]
        length = length - 1
    return s1

s = 'This is a challenge'
print(reverse1(s))
print(reverse2(s))
print(reverse3(s))
print(reverse4(s))
print(reverse5(s))

• 首先要先知道 Python 的 str 是沒有 reverse方法的呀！(不能直接 <string>.reverse())
• reverse1 是效能最好也是最方便的，也就是運用 Python 的 Slicing。Slicing 可以讓我們擷取字串，例如 'abcde'[1:3] 會把 index 1~2 (不包含 3) 的字擷取出來，變成 bc 。定義上 [start:stop:step] ， start 就是起始的 index， stop 就是終止的 index (不含 stop 這個 index)， step 是間隔，假設沒填預設就是 1。而這裡的 [::-1] 沒填 start跟 stop 時，start 跟 stop 就是最開始跟最尾巴，而 -1 就代表從尾巴開始往回走，且每次走一個 index，所以如果用 cat 來當例子，就會是 tac 啦！(從 t 開始往回每次走一步)
  reverse2 的邏輯就是用 for loop 去 iterate 字串，從字首開始，每次取一個 character c，接著每次把拿到的 character 跟 r 串接，而且是 c 在左邊， r 在右邊，這樣如果以 cat為例，就會是'c' + '' => 'a' + 'c' => 't' + 'ac' => 'tac'
• reverse3 是先把字串轉成 list，再借用 list 的 reverse() Method，把 list 內的元素反轉，在把這些元素串接起來。串接起來我們用 ''.join(r) ， r 是 list，而 '' 是說這些元素要透過什麼接起來，假設今天以 cat 為例，而改成 '-'.join(r) ，那麼就會變成 t-a-c 。
• reverse4 中的 reversed 是一個內建函數，可以傳入字串並得到一個 Iterator，這個 Iterator 被 iterate 的時候，會反向地返回元素。而這裡我們一樣用剛才用到的 join 。可以想成 join 在執行時，就是將 reversed(s) iterate 到的值，去做連接的動作。所以如果是 cat 就會是 t join a join c 變成 tac 囉！
• reverse5 這裡運用 while 。 len(s) 是字串的長度。整個概念上是從最後一個字開始，反向地把每個字取出來並且連接在一起，記得要確定終止條件最終會達成，不然會出現無限迴圈唷！

Golang

package main

import "fmt"
import "strings"

func reverse1(s string) string {
  runes := []rune(s)
  for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
    runes[i], runes[j] = runes[j], runes[i]
  }
  return string(runes)
}

func reverse_words(s string) string {
	words := strings.Fields(s)
	for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
		words[i], words[j] = words[j], words[i]
	}
	return strings.Join(words, " ")
}

func main() {
  fmt.Println(reverse1("This is a challenge"))
  fmt.Println(reverse_words("This is a challenge"))
}

• 在 Golang 並沒有內建 reverse 的 Method。而我們這邊會有一種最常見的方式 (幾乎沒有其他方式)，來解決這個問題。
• 在 reverse1，我們把參數 s (string) 轉換成 Array of Rune，這是因為 string 在 Golang 是 immutable，我們沒辦法直接把某個 string 把它反轉後還存在同一個 string。所以這邊我們把 s 轉換成 []rune 也就是 Array of rune，就變成是 Mutable 的 Array。 rune 是 int32 ，也就是四個 Bytes，這裡轉換成 []rune 是因為 Golang 內部是以 utf-8 來編碼。如果我們的 s 含中文字，例如 “你好”，當我們用 len 去取得 s 的長度會看到結果是 6，不是 2，那是因為對 string 取 len 會得到的是實際上的 Bytes (string 底層是 Array of Byte)，而一個中文字是 3個 Byte。所以我們必須將 string 轉成 Array of Rune，這樣才能以 utf-8 的角度來得到字串真正的字數。這裡我們來實際用個例子 abcde ，進到 for-loop 的時候， i 為 0，而 j 為 len(runes)-1 ，這邊同時對 i 和 j 賦值，並且一起處理，就不用寫出巢狀的迴圈。而繼續運行的條件是 i < j ，每次做完一圈 i 就會加 1，而 j 會減 1 (越來越靠近)。再來我們看到主要的邏輯是每次把 index 為 i 跟 j 的字交換，所以實際執行上會是 abcde => ebcda ( i = 0, j = 4) => edcba ( i = 1, j = 3) => 終止 ( i = 2, j = 2, i < j 不成立)。
• 因為 Golang 這裡只講了一種方法，我們來加碼一個題目，假使我們要 reverse words 呢？例如 This is a challenge ，我們想變成 challenge a is This 。我們來看 reverse_words 這個 Function。概念上差不多，只是我們這邊不是 Array of Rune，而是 Array of string， strings.Fields(s) 是透過 strings 這個內建的 Package 裡的 Fields 這個 Function 來把原來的 String 以空白做分隔去切出字來，變成 Array of string。再來的做法就跟 reverse1 的想法一樣。當我們得到反轉後的 Array of string，再透過 strings 另外的 Function Join 把這些字重新接起來 (字與字之間會是一個空白，也就是 Join 的第二個參數。

Rust

fn reverse1(input: &str) -> String {
    let mut result = String::new();

    for c in input.chars().rev() {
        result.push(c)
    }

    result
}

fn reverse2(input: &str) -> String {
    input.chars().rev().collect()
}

fn main() {
  let s = "This is a challenge";
  println!("{}", reverse1(s));
  println!("{}", reverse2(s));
}

• Rust 的 string 也是沒有直接內建 Reverse 的方法，讓我們來看看這邊所列的兩種方式囉！
• reverse1 是先產生一個新的 Empty String (透過 String::new())，而綁定到 result ，這裡是 mut 因為我們要把字塞進去。接著 call input 這個的 chars 的方法，可以得到一個 Iterator of Chars(如果忘了 Iterator 是什麼可以回到前一天去複習)，這裡的 Char 是 Unicode Value，所以是 32 bits，不同於其他語言的 Char 通常是 8 bits，因為轉換成 Iterator of Chars，就不用擔心例如中文的問題。 而當我們 invoke 這個 Iterator 的 rev() 後，這個 Iterator 就會變成從右往左 interate。然後我們就可以把每次得到的 Char 透過 String 的 Function push 把 c 一個一個塞到 result 這個 String 囉！
• reverse2 更簡單，直接在 input.chars().rev() 之後，直接再 invoke collect() 來得到反轉過後 String 囉！
• 這裡我們看到怎麼又有 &str 又有 String 呢？這兩個有什麼不同？ str 是 immutable fixed-length string，而常以 &str 這種 borrowed type 的形式在 Function 間傳遞。至於 String 則是可變長度，mutable。可以參考這裡 囉！

結語

今天寫完這些有點累，不過還滿實用的，可以在每個語言去看到他們解決這個問題的不同角度跟方式。那我們明天見囉！