---
# System prepended metadata

title: 6. ZigZag Conversion
tags: [leetcode, '6', medium]

---

# 6. ZigZag Conversion

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

## :memo:  Question
![](https://i.imgur.com/NyWQiQF.png)
![](https://i.imgur.com/0W2BwZq.png)



## :memo: My first solution
* :medal: **思考一**: 這題在考你怎麼推出他的每一列邏輯是怎麼推算出來的，我們用他給的例子來推，如圖下:
![圖一](https://i.imgur.com/VSF1aGn.png)

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

> :bulb: 怎麼推出**2n-2 (n = numRows)**
>![](https://i.imgur.com/HMY1Ewq.png)


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


## :memo: Code

```python=
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)
