LC 6. Zigzag Conversion

https://leetcode.com/problems/zigzag-conversion/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        int n = s.size();
        string ans = "";
        for (int i = 0; i < numRows; i++) {
            int index = i;
            int base = (numRows - 1) * 2;
            int plus = base - i * 2;
            while (index < n) {
                if (plus == 0) plus = base;
                ans.push_back(s[index]);
                index += plus;
                plus = base - plus;
            }
        }
        return ans;
    }
};

Time Complexity: O(n)
Space: O(n)

透過觀察可以使用計算的方法直接知道下個字應該要是什麼，這樣就可以不用真的去創建一個 zigzag 的陣列。