O(N) python solution in 8 lines


  • 0
    C

    Short solution but requires a lot of math. If the zigzag has period T, then every index in row r is equal to either r or -r (mod T). For example:

    0     6     12  # 0 (mod 6)
     1   5 7   11   # 1 or -1 (mod 6)
      2 4   8 10    # 2 or -2 (mod 6)
       3     9      # 3 (= -3) (mod 6)
    

    The indices in a given row also alternate between r and -r (mod T). To get from index i to the next index in the row, we can add an amount q which satisfies i + q = -i (mod T) and 0 < q <= T. With a bit of massaging we get q = T - (2*i % T). Once we get this the code is real simple.

    class Solution(object):
        def convert(self, s, numRows):
            ret = ''
            T = max((numRows - 1)*2, 1) # period of one zigzag
            for r in range(numRows):
                i = r
                while i < len(s):
                    ret += s[i]
                    # increase by an amount q that satisfies
                    #  i + q = -i (mod T)  and  0 < q <= T
                    i += T - (2*i % T)
            return ret
    

Log in to reply
 

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