6. Zigzag Conversion

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