[Top Interview 150] 6. Zigzag Conversion
Solution)
class Solution:
def convert(self, s: str, numRows: int) -> str:
# Edge Case
if numRows == 1: return s
# Initialization
res = {}
for i in range(numRows):
res[i] = []
# Add characters according to its row
char, row = 0, 0
while char < len(s):
while row < numRows-1 and char < len(s):
res[row].append(s[char])
row += 1
char += 1
while row > 0 and char < len(s):
res[row].append(s[char])
row -= 1
char += 1
# Gather all the characters in one list
for i in range(1, numRows):
res[0].extend(res[i])
del res[i]
# Return string of the gathered list
return ''.join(res[0])
Problem: LeetCode
Time Complexity: O(n+m)
Space Complexity: O(n+m)
* n = len(s), m = numRows
Explanation)
We'll have a dictionary that will save the characters according to their rows.
For example, if s = "PAYPALISHIRING" and numRows = 4, the zigzaged version is,
P I N
A L S I G
Y A H R
P I
0th row is [P, I, N]
1st row is [A, L, S, I, G]
2nd row is [Y, A, H, R]
3rd row is [P, I]
We'll save the characters of s just like the above.
Edge Case)
When numRows is 1 there is nothing to do other than returning s by itself, so we just return s.
def convert(self, s: str, numRows: int) -> str:
if numRows == 1: return s
Initialization)
As explained earlier, we'll have a dictionary that will save characters in a list according to its row.
So we'll have the number of rows as key and empty lists for their values.
Then as we iterate s, we'll save the characters to their rows' lists.
def convert(self, s: str, numRows: int) -> str:
if numRows == 1: return s
res = {}
for i in range(numRows):
res[i] = []
Saving characters from 0 to numRows-2)
First, set two indexes char and row.
char will indicate the characters of s.
row will indicate the rows in res.
Then we'll zigzag iterate s and this step will show how to add characters in row 0 to numRows-2.
Don't forget to always check if char index didn't go over s!
Once you add the current character, update the indexes to add other characters.
def convert(self, s: str, numRows: int) -> str:
if numRows == 1: return s
res = {}
for i in range(numRows):
res[i] = []
char, row = 0, 0
while char < len(s):
while row < numRows-1 and char < len(s):
res[row].append(s[char])
row += 1
char += 1
Saving characters from numRows-1 to 1)
After adding the characters that are loacted in row 0 to numRows-2,
it's time to add characters that are located in row numRows-1 to 1.
def convert(self, s: str, numRows: int) -> str:
if numRows == 1: return s
res = {}
for i in range(numRows):
res[i] = []
char, row = 0, 0
while char < len(s):
# Adding characters in row 0 to numRows-2
while row > 0 and char < len(s):
res[row].append(s[char])
row -= 1
char += 1
Gather all the characters)
Once we have all the zigzaged characters in res dictionary, it's time to put all of them together.
Since the characters are already in a proper order, we just need to gather all the characters in the 0th row list.
After we put all the characters in the 0th row, we return the string version of the 0th row.
def convert(self, s: str, numRows: int) -> str:
if numRows == 1: return s
res = {}
for i in range(numRows):
res[i] = []
char, row = 0, 0
while char < len(s):
# Zigzag adding characters to numRows
for i in range(1, numRows):
res[0].extend(res[i])
del res[i]
return ''.join(res[0])
This problem was the hardest string problem as the number of dislike tells you haha. But compared to other problems with this many dislikes, it was a lot easier. Now I'm done with all the medium problems in string/array section. Next problem is going to be two pointers, which I'm also confident with. See you then!