class Solution: def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ # The best way to understand and formulate the solution is draw a grid and see how it works to fill the grid in a zigzag. # The complexity of this algorithm is O(n). It captures and traverses each element only once in the string. if numRows <= 1: return s str = '' i = 0 for i in range(numRows): if numRows -1 == i: # Here we say if its the last row we know the interval where the pattern will repeat. m = 2 * i else: m = 2*(numRows - (i+1)) # In other case we need to formulate the interval like this as well. j = i while j < len(s): # Loop through until the row elements are extracted. str += s[j] if i % numRows != 0: if j+m < len(s): str += s[j+m] # Locate the next char with the m interval. j += m + 2 * i # Jump to the next candidate. else: j += m # The first and last elements treated differently. return str
A Python solution with O(n) complexity
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.