# [6\. Zigzag Conversion](https://leetcode.com/problems/zigzag-conversion/)

:::spoiler Solution

class Solution {
public:
    string convert(string s, int numRows) {
        // 考慮 base case
        if (numRows <= 1) return s;
        
        string res;
        int n = s.size();
        
        // 建立一個 vector 儲存字母
        vector<string> stringVector(numRows);
        
        int i = 0;
        while (i < n) {
            // 當 pos 小於 numRows 的時候，將 s[i] 加到 stringVector 裡
            // Z 字形，由上往下的部分
            for (int pos = 0; pos < numRows && i < n; ++pos) {
                stringVector[pos] += s[i];
                i++;
            }
            // pos 從 numRows - 2 遞減，最少到 1
            // Z 字形，由下往上的部分
            for (int pos = numRows - 2; pos >= 1 && i < n; --pos) {
                stringVector[pos] += s[i++];
            }
        }

        // 將字串 join 在一起
        for (auto& a : stringVector) {
            res += a;
        }
        return res;
    }
};

- T: $O(numRows \cdot n)$
- S: $O(numRows \cdot n)$
:::