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"
Constraints:
1 <= s.length <= 1000s consists of English letters (lower-case and upper-case), ',' and '.'.1 <= numRows <= 1000
The description was taken from https://leetcode.com/problems/zigzag-conversion/.
#O(N) Time, O(N) Space
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or len(s) < numRows:
return s
output = [[] for row in range(numRows)]
direction = -1
row = 0
for char in s:
output[row].append(char)
if row == 0 or row == numRows -1:
direction *= -1
row += direction
for i in range(len(output)):
output[i] = "".join(output[i])
return "".join(output)Similar to how we would perform a level-order traversal on a tree, we can create a matrix equal to the number of rows, and append the characters to the corresponding row array. During the iteration, we will keep track of the current row we are on, and if we have reached the beginning or end of the row, we will multiply the row counter by the direction by a negative one so that we can turn around.
Once we have finished appending the characters to each row, we will join each row to form a string, and then join those strings to form the output.
First off, if the number of rows is one, then that is just the string in one row. If the length of the string is less than the number of rows, then that is just one column. In both cases, the resulting string will be the exact same.
if numRows == 1 or len(s) < numRows:
return s
Otherwise, we will create our output matrix with the length equal to the number of rows.
output = [[] for row in range(numRows)]
We will set our initial direction to negative one, this will be explained later, and our initial row to zero.
direction = -1
row = 0
Then, for each character in the string, we will append the current character to the current row place.
for char in s:
output[row].append(char)
If we have come up to the top row or gone down to the bottom row, we will need to switch directions. We will do this by multiplying the current direction by negative one.
if row == 0 or row == numRows -1:
direction *= -1
By doing this, if we were incrementing the row before, we will be decrementing it now. If we were decrementing it before, we will be incrementing it now.
This is also the reason why we started it off at negative one so that the starting product will be one and we will begin incrementing the row.
row += direction
Once we have all of our characters in the matrix rows, we will iterate through the rows and join each row into a string.
for i in range(len(output)):
output[i] = "".join(output[i])
Once we have a single array of strings, we will join those strings together to form our output string.
return "".join(output)