Easy Python O(n) Solution(94%) with explanations


  • 4
    R

    After some observations, it's easy to find the floor of a letter is periodical. Take n == 4 as an example. If we look at the index % 6, we have a(0)b(1)c(2)d(3)e(4)f(5) ...
    so 2*(numRows-1) will be the period.
    Note: 1,5 should both go to floor 1. 2,4 should both go to floor 2, etc..

    class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1:
            return s
        # calculate period
        p = 2*(numRows-1)
    
        res = [""] * numRows
        for i in xrange(len(s)):
            floor = i%p
            if floor >= p//2:
                floor = p - floor
            res[floor] += s[i]
        return "".join(res)

  • 0
    T

    Nice solution. I think you can save a line by using "period = 2*k-2 or 1" and replace p//2 by numRows.


  • 0
    R

    thanks for your suggestion. but in period = 2*k -2 or 1, how k is defined?


Log in to reply
 

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