Easy Explanation with Example: Python O(N)


  • 0
    J

    Understand the patterns in zigzag.

    A     G
    B   F H
    C E   I 
    D     J
    

    Row 0: the gap between A-G is 6 so it goes 6-6-6-6
    Row 1: the gap between B-F-H is 6 so it goes 4-2-4-2
    Row 2: the gap between C-E-I-K is 6 so it goes 2-4-2-4
    Row 3: the gap between D-J is 6 so it goes 6-6-6-6

    The gap in the top(6) is (nRow-1) * 2 so the example above nRow=4, gap = 6. Each index jumps to next with this pattern (gap - prev jump). The only thing to be careful is that when the jump becomes 0 which will not jump to the next.

        def convert(self, s, numRows):
            if numRows == 1 or len(s) <= numRows:
                return s
            
            row = 0
            ret = []
            # Get the gap
            gap = (numRows -1) * 2
    
            while numRows > 0:
                count = 1
                subJump = (numRows -1) * 2
                # make sure there is 0 jump
                if (subJump == 0):
                    subJump = gap
                start = row
    
                ret.append(s[row])
                # move to next pattern 4-2-4-2-4-2
                while len(s) > (start + subJump):
                    ret.append(s[start + subJump])
                    start += subJump
                    subJump = gap - subJump
                    # make sure there is 0 jump
                    if (subJump == 0):
                        subJump = gap
                    
                numRows -= 1
                row += 1
            
            return ''.join(ret)
    

Log in to reply
 

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