This is my solution forZigZag Conversion, a coding challenge from LeetCode.
The challenge:
Write a program that takes two parameters, a string and a number ofrows, that interprets the string as if it were displayed in a zigzagpattern and returns a line by line conversion of this interpretationin a final answer string.
Example:
Given the string 'PAYPALISHIRING', and 3 rows:
P A H NA P L S I I GY I RThe program should output:
"PAHNAPLSIIGYIR"
My approach was to use a list of dictionaries, with the dictionaries as columns and their position in the list representing row positions. At the end of the control flow the list of dictionaries is unpacked and returned in the final output string.
My solution:
class Solution(object): def convert(self, s, numRows): row = numRows if row <= 1: return(s) else: a_lst = [] a_dict = {} outer_count = 0 loop_count = 0 my_count = 0 inner_count = row if row == 2: minus = 0 else: minus = 2 for i in s: loop_count+=1 if outer_count < row: outer_count+=1 a_dict[outer_count] = i if outer_count == row: my_count = 0 inner_count = row dict_copy = a_dict.copy() a_lst.append(dict_copy) a_dict.clear() elif loop_count == len(s): dict_copy = a_dict.copy() a_lst.append(dict_copy) a_dict.clear() elif my_count < row - minus: my_count+=1 if row == 2: inner_count = my_count else: inner_count-=1 a_dict[inner_count] = i if my_count == row - minus: outer_count = 0 dict_copy = a_dict.copy() a_lst.append(dict_copy) a_dict.clear() elif loop_count == len(s): dict_copy = a_dict.copy() a_lst.append(dict_copy) a_dict.clear() my_count = 1 my_str = '' while my_count <= row: for d in a_lst: for key in d: try: my_str+=(d[my_count]) break except KeyError: break my_count+=1 return(my_str)I would like any suggestions on improving code readability or conditional control logic. I would also like to know if I missed any edge cases. Thank you.
1 Answer1
DRY. Every path through the loop ends up in
dict_copy = a_dict.copy() a_lst.append(dict_copy) a_dict.clear()Lift it out out of the conditionals. You will also immediately see that the branches
oop_count == len(s)become no-ops, and could be safely removed, along with now irrelevantloop_count. The loop now looks a bit more manageable:for i in s: if outer_count < row: outer_count+=1 a_dict[outer_count] = i if outer_count == row: my_count = 0 inner_count = row elif my_count < row - minus: my_count+=1 inner_count-=1 a_dict[inner_count] = i if my_count == row - minus: outer_count = 0 dict_copy = a_dict.copy() a_lst.append(dict_copy) a_dict.clear()Still, it is a textbook example of spaghetti. I must admit I failed to follow the control flow.
Special casing of
row==2is extremely suspicious. I don't see why it should be a special case. If it should indeed, it is a trong indication that the algorithm is flawed.Speaking of the algorithm, it seems overcomplicated. As far as I can tell, the point of this exercise is to determine a pattern of indices. For example, consider a case of 5 rows. The zigzag table looks like
0 8 16 1 7 9 15 17 2 6 10 14 18 ... 3 5 11 13 19 4 12 20Take e.g. a row 1 (
1, 7, 9, 15, 19, ...). See that the differences alternate between6and2.Prove (or at least convince yourself) that it is the case. Whatever
numRowsis, the indices' deltas in therowalternate between(numRows - row - 1) * 2androw * 2. Once you do it, the construction of the output string is trivial, and does not require any heavy-weight structures like dictionaries (or the list of them).
- \$\begingroup\$Thanks! I should first look for a pattern, I just sort of eye-balled it and made an attack at the first idea that seemed to work. I should think these out much more. Any tips on how I could better approach such problems? Also what is DRY?\$\endgroup\$Tim_Jarvis99– Tim_Jarvis992021-10-04 17:44:41 +00:00CommentedOct 4, 2021 at 17:44
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.