# ZigZag Conversion

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

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();
}
}```