LeetCode #6 ZigZag Conversion

記錄 LeetCode #6 ZigZag 思考解法的過程筆記，並使用 Go 來實作。

LeetCode #6

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (see leecode page or below example).

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

簡單的說，要使用鋸齒形狀來排字串，然後文字的位置，來取得新的字串。因此得先畫一下圖，假設 text 還是一樣是 PAYPALISHIRING，只是其 nRows 改成 4 行，因此排序字串可以畫出以下的圖 (節省空間的鋸齒型示意圖)：

因此其轉換後的字串，由上到下由左至右一行一行讀取，會是 PIN-ALSIG-YAHR-PI，其結果字串應該要是 PINALSIGYAHRPI。最簡單的解法思路是建立 nRows 字串陣列，然後一個一個根據規則塞入到該些字串，最後再將該些字串串在一起的解答：

import(
   "strings"
)

func convert(s string, numRows int) string {
   if (numRows <= 1){
      return s
   }
   
   cs := make([]string, numRows);
   idx := 0
   step := 1
   for _, c := range s{
      cs[idx] += string(c)
      idx += step
      if idx >= numRows {
         step *= -1
         idx = numRows - 2
      }else if idx < 0{
         step *= -1
         idx = 1
      }
   }
   
   return strings.Join(cs[:], "")
}

但是非常浪費記憶體空間的做法，而且需要反覆的記憶體操作，速度會比較慢。但既然是讀取字串，那麼將上圖轉換成字串的索引，String index，只要找到這 index 的規則，那麼便能較優雅解決這個問題：

假設 nRows 共有 n 行，那麼其表應該會是如此：

為什麼會是這樣？假設一開始是這個狀態，求 X 是多少？我們知道共有 n 列，共有 n 個數字，因此 (X) - (0) + 1 = n：

接著求 Y，同理，原先 X 走到 Y 一樣有 n 個數字，因此走 n-1…，得知 Y = X + (n-1) = 2n-2，以此類推：

因此觀察其 Index 模式，可得知從青色格子走到亮綠色格子，需要 2*[(n-1)-(2)]，而亮綠色格子到紅色格子剛好是 2 * (2)：

因此設定目前在第 k 列，其數字變化會是如此，然後去驗證一開始的表：

• k
• k + 2*(n-k-1)
• k + 2*(n-k-1) + 2*k
• k + 2*(n-k-1) + 2k + 2(n-k-1)
• k + 2*(n-k-1) + 2k + 2(n-k-1) + 2*k
• …and so on

發現完全符合，已經找到其 index 變化模式，便可以改寫程式碼，完成這一次的數學歸納試煉…：

import(
   "bytes"
)

func convert(s string, numRows int) string {
   if (numRows <= 1){
      return s
   }
   
   var b bytes.Buffer
   for k := 0; k < numRows; k++{
      oft1 := 2 * (numRows - k - 1)
      oft2 := 2 * k
      idx := k
      b.WriteString(string(s[idx]))
      for idx < len(s){
         if oft1 > 0 {
            idx += oft1
            if idx < len(s){
               b.WriteString(string(s[idx]))
            }
         }
         if oft2 > 0 {
            idx += oft2
            if idx < len(s){
               b.WriteString(string(s[idx]))
            }
         }
      }
   }   
   return b.String()
}

在撰寫這篇回顧時，才熊熊想起可以使用那最直覺的方法來解決這問題，也許真的是被訓練到一定要找到自己認為的最佳解，太優化過頭了…。