# Question

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

$$O(n)$$ time and space complexity solution by rearranging characters into the final string.

Each row’s character starts at $$r$$th character in the string. The gap between two columns are $$2*(N_r-1)$$. Between two columns there will be one or two gaps. If there’s only one gap, the gap size is $$2*(N_r-1)$$. If there are two gaps, the first gap is of size $$2*(N_r - r - 1)$$ and the second gap is of size $$2*r$$, where $$N_r$$ is total number of rows and $$r$$ is the 0-based row number.

class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows == 1:
return s

gap = 2 * (numRows - 1)
out = list()
for row in range(0, numRows):
firstGap = gap - 2 * row
secondGap = 2 * row
i = row
round = 0
while i < len(s):
out.append(s[i])
if firstGap == 0 or secondGap == 0:
i += max(firstGap, secondGap)
elif round % 2 == 0:
i += firstGap
else:
i += secondGap
round += 1

return ''.join(out)