# ZigZag Conversion Problem

Difficulty: Medium

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

Example 3:

Input: s = “A”, numRows = 1
Output: “A”

## Problem solution in Python

``````class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or numRows >= len(s):
return s
delta = -1
row = 0
res = [[] for i in range(numRows)]
for c in s:
res[row].append(c)
if row == 0 or row == numRows - 1:
delta *= -1
row += delta
for i in range(len(res)):
res[i] = ''.join(res[i])
return ''.join(res)
``````

## Problem solution in Java

``````class Solution {
public String convert(String s, int numRows) {
if (s.length() == 0 || s.length() == 1 || numRows == 0 || numRows == 1)
return s;
int cols = (s.length()+numRows-1 -1)/(numRows - 1);

String ans = "";
int col = 0, row = 0;
while (row < numRows){
col = 0;
while (col <= cols){
if (col % 2 == 0){
if (col*(numRows - 1)+row < s.length())
ans += s.charAt(col*(numRows - 1)+row);
}else{
if (col*(numRows - 1)+numRows - 1 - row < s.length())
ans += s.charAt(col*(numRows - 1)+numRows - 1 - row);
}
if (row == 0 || row == numRows -1)
col+=2;
else col++;
}
row++;
}
return ans;
}
}

``````

## Problem solution in C++

``````string convert(string s, int numRows)
{
if(numRows == 1)
{
return s;
}

vector<vector<char>> v(numRows, vector<char>());

int row = 0;
int step = 0;

for(int i = 0; i < s.length(); i++)
{
v[row].push_back(s[i]);

if(row == 0)
{
step = 1;
}
else if(row == numRows - 1)
{
step = -1;
}

row += step;
}

string result;

for(int i = 0; i < numRows; i++)
{
result.append(v[i].begin(), v[i].end());
}

return result;
}
``````

## Problem solution in C

``````char * convert(char * s, int numRows){
char conv[1000];
int i, j, m, n, x, y, gap;

if (numRows == 1)
return s;

n = numRows - 1;
m = strlen(s);
x = 0;

for (i = 0; i < numRows; i++) {
for (y = i, j = 0; y < m; y += gap, j++) {
conv[x++] = s[y];
gap = (n - ((j+1)&1)*(i%n) - (j&1)*((n-i)%n)) << 1;
}
}

memcpy(s, conv, m);

return s;
}
``````