Link to Question

MEDIUM

Zigzag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

• string convert(string s, int numRows)

Example

Input:

s = "PAYPALISHIRING", numRows = 3

Output:

"PAHNAPLSIIGYIR"

---

Constraints

• 1 ≤ s.length ≤ 1000
• 1 ≤ numRows ≤ 1000

---

Solution: Simulation

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(n), for storing the rows.

C++

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> r(numRows);
        int index = 0, step = 1;
        for (auto c : s) {
            r[index] += c;
            if (index == 0) step = 1;
            else if (index == r.size() - 1) step = -1;
            index += step;
        }
        string ans;
        for (auto& c : r) ans += c;
        return ans;
    }
};