Approach 1

sort by row

we iterate every litter in the string, sorted by different row, then join all the rows together.

C++ code

class Solution {
public:
    string convert(string s, int n) {

        if (n == 1) return s;

        vector<string> rows(min(n, int(s.size())));
        int curRow = 0;
        bool goingDown = false;

        for (char c: s){
            rows[curRow] += c;
            if (curRow == 0 || curRow == n - 1) goingDown = !goingDown;
            curRow += goingDown? 1: -1;
        }

        string ret;
        for (string  row: rows) ret += row;

        return ret;
    }
};

Approach 2

visit by row

noticing that each row follows a certain pattern. we can use the pattern to visit every row.

C++ code

class Solution {
public:
    string convert(string s, int n) {

        if (n == 1) return s;

        string res;
        int cycleLen = 2 * n - 2;

        for (int i = 0; i < n; i++){
            for (int j = 0; j + i < s.size(); j += cycleLen){
                res += s[i + j];
                if (i != 0 && i != n - 1 && j + cycleLen - i < s.size())
                    res += s[j + cycleLen - i];
            }
        }

        return res;
    }
};