The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"


Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"


Explanation:

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

Solution 1 in C++

#include <iostream>


using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        string a[numRows];
        int str_len=s.length();
        int i;
        int pos=0;
        int direction=1;
        int turning_point;
        string ret;

        turning_point=numRows-1;

        for( i=0; i<str_len; i++) {
            a[pos] += s[i];
            if (pos==turning_point) {
                if (numRows<3)
                    pos=0;
                else {
                    direction *= -1;
                    if (direction<0) {
                        turning_point=(numRows>2)?1:0;
                        pos=numRows-2;
                    } else {
                        turning_point=numRows-1;
                        pos=0;
                    }
                }
            }
            else pos += direction;
            cout << s[i] << " " << pos << " " << direction << " " << turning_point << endl;
        }
        for( i=0; i<numRows; i++) {
            ret += a[i];
            cout << a[i] << endl;
        }
        return ret;
    }
};

int main(void)
{
    Solution s;
    string testcase = "PAYPALISHIRING";

    cout << testcase << "(3) -> " << s.convert( testcase, 3) << " : Expected = PAHNAPLSIIGYIR" << endl;

    cout << testcase << "(4) -> " << s.convert( testcase, 4) << endl;

    return 0;
}

Solution 2 in C++

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

        if (numRows == 1) return s;

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

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

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

Solution 3 in Java

class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++)
            rows.add(new StringBuilder());

        int curRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }

        StringBuilder ret = new StringBuilder();
        for (StringBuilder row : rows) ret.append(row);
        return ret.toString();
    }
}