---
# System prepended metadata

title: 6. ZigZag Conversion
tags: [LeetCode]

---

---
tags: 'LeetCode'
---
# 6. ZigZag Conversion
https://leetcode.com/problems/zigzag-conversion/
## 題目敘述
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
```
P   A   H   N
A P L S I I G
Y   I   R
```
And then read line by line: "PAHNAPLSIIGYIR"

## Example
Example 1:
```
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
```
Example 2:
```
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
```
Example 3:
```
Input: s = "A", numRows = 1
Output: "A"
```
## 解題想法
### 1.
```
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
P   A   H   N
A P L S I I G
Y   I   R
```
numRows = 3
P A Y P A L I S H I R I N G
1 2 3 2 1 2 3 2 1 2 3 2 1 2

numRows = 4
P A Y P A L I S H I R I N G
1 2 3 4 3 2 1 2 3 4 3 2 1 2

經觀察知行數沿str遞增到numRows，然後遞減至1，不停重複
於是只要檢查當前行數(curROW)是否為
(1)==numRows
(2)==1
便知是否反轉
```
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1)
        {
            return s;
        }
        
        string ans = "";
        vector<string> rows(numRows, "");
        int curRow = 0;
        bool goingdown = false;
        
        for (char c : s)
        {
            rows[curRow] += c;
            if (curRow == numRows - 1 || curRow == 0)
            {
                goingdown = !goingdown;
            }
            if (goingdown)
            {
                curRow++;
            }
            else
            {
                curRow--;
            }
        }
        for (string a:rows){
            ans += a;
        }
        return ans;
    }
};
```
時間複雜度O(N)

