A Python solution with O(n) complexity


  • 0
    M
    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.