Leetcode - 6. 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"
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.
T(N) = O(N) n is the length of the string
S(N) = O(N) we visited all item once
Comments
Post a Comment