Leetcode - 6. ZigZag Conversion

6. ZigZag Conversion

Medium

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"

Solution : 

numRows will keep our base structure by using multiple numRows time.

we can keep an output array : 

output = [""] * numrows

means output will be = [ " " ," " ," " ]

and we can fill up in this array by using iterative

our structer like : 

s = "PAYPALISHIRING", numRows = 3

line 0 = P     A      H      N

-------------------------------

line 1 = A  P  L  S   I   I  G

-------------------------------

line 2 = Y     I      R

we can increment from 0 to 2 the 'line'. 

When we reach line 2 means = (numrows - 1)  we can decrease the line and the line param can go to line 1.

output[line(0)] += s[0]

output[line(1)] += s[1]

output[line(2)] += s[2]

output = ["P","A","Y"]

and 

output[line(1)] += s[3]

output = ["P","AP","Y"]

and we reach again line 0

output[line(0)] += s[4]

output = ["PA","AP","Y"]

so on...

But numRows is 1 we don't need to go to back up and down line variable. 

class Solution: def convert(self, s: str, numRows: int) -> str: if not s: return "" if len(s) == 0: return "" line = 0 pre_line = 1 output = [""] * numRows for i in range(len(s)): output[line] += s[i] if numRows > 1: line += pre_line #already reach up or down we can extract the line from pre_line so we can multiple -1 if line == 0 or line == numRows -1: pre_line *= -1 return "".join(output) s = "PAYPALISHIRING" numRows = 3 res = Solution().convert(s, numRows) print("res : " , res)

T(N) = O(N) n  is the length of the string

S(N) = O(N) we visited all item once

Success

Details 

Runtime: 48 ms, faster than 96.40% of Python3 online submissions for ZigZag Conversion.

Memory Usage: 14.4 MB, less than 71.41% of Python3 online submissions for ZigZag Conversion.