6. ZigZag Conversion

O(n) time O(n) space
用辅助字符串组来保存每一行的字符串，通过调整step来决定是从上往下放字符还是从下往上放字符，当指针指向第一行则从上往下，当指针指向最后一行则从下往上

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows <= 1 or numRows >= len(s): return s
        v = [''] * numRows
        # v = ['' for i in range(numRows)]
        i, step = 0, -1
        for c in s:
            if i == numRows - 1:
                step = -1
            elif i == 0:
                step = 1
            v[i] += c
            i += step
        return ''.join(v)

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> v(numRows);
        int i = 0, step = -1;
        for (char c : s) {
            if (i == numRows - 1) {
                step = -1;
            } else if (i == 0) {
                step = 1;
            }
            v[i] += c;
            i += step;
        }
        string res;
        for (const auto &str : v) {
            res += str;
        }
        return res;
    }
};