# 6. ZigZag Conversion

###### tags: `leetcode` `6` `medium`

## :memo: Question

## :memo: My first solution
* :medal: **思考一**: 這題在考你怎麼推出他的每一列邏輯是怎麼推算出來的，我們用他給的例子來推，如圖下:

* 第0列與第n列(紅色)明顯與中間這些列(藍色)的邏輯是不同的，因此第0列與第n列的要一起算。第0列與第n列的下一個字母所在的位置是 **2n-2 (n = numRows)**

> :bulb: 怎麼推出**2n-2 (n = numRows)**
>

* :medal: **思考二**:中間這些列(藍色)的下一個字母所在位置是**2n-2-2i 與 2i** (i指的是他是第幾列)
> :bulb: 怎麼推出**2n-2-2i 與 2i**
> 

## :memo: Code

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 注意如果 numRows == 1 時，要獨立討論
        if numRows == 1:return s
        
        ans = ""
        for i in range(numRows):
            if i == 0 or i == numRows-1:
                while i < len(s):
                    ans += s[i]
                    i += 2*numRows-2
            else:
                # count 用來算上圖紅色的地方，中間的列加的次數會影響他的公式
                count = 0
                current = i
                while i < len(s):
                    ans += s[i]
                    if count % 2  == 0:
                        i += 2*numRows-2-2*current
                    else:
                        i += 2*current
                    count += 1
                    
        return ans

## :memo: bigO
* 時間複雜度: O(n)，n==len(s)
* 空間複雜度: O(n)，如果不算給出答案的 array 的話是 O(1)