---
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)