Python O(n) Solution in 96ms (99.43%)


  • 55
    D
    class Solution(object):
        def convert(self, s, numRows):
            """
            :type s: str
            :type numRows: int
            :rtype: str
            """
            if numRows == 1 or numRows >= len(s):
                return s
    
            L = [''] * numRows
            index, step = 0, 1
    
            for x in s:
                L[index] += x
                if index == 0:
                    step = 1
                elif index == numRows -1:
                    step = -1
                index += step
    
            return ''.join(L)

  • 13
    H

    Good solution.Based on your idea. more concise:

    class Solution(object):
    def convert(self, s, numRows):
        step = (numRows == 1) - 1  # 0 or -1  
        rows, idx = [''] * numRows, 0
        for c in s:
            rows[idx] += c
            if idx == 0 or idx == numRows-1: 
                step = -step  #change direction  
            idx += step
        return ''.join(rows)

  • 0
    D

    Good idea! Thanks


  • 0
    B

    cool!.......................................


  • 2
    Q

    I just did some testing (python 3.5.1), with below functions.

    def convert(s, numRows):
        if numRows<2 or len(s)<numRows: return s
        rows = [""]*numRows
        ind, step = 0, 1
        for v in s:
            rows[ind] += v
            if ind == 0: step = 1
            elif ind == numRows-1: step = -1
            ind += step
        return ''.join(rows)
    
    def convert2(s, numRows):
        if numRows<2 or len(s)<numRows: return s
        rows = [[] for _ in range(numRows)]
        ind, step = 0, 1
        for v in s:
            rows[ind] += v
            if ind == 0: step = 1
            elif ind == numRows-1: step = -1
            ind += step
        return ''.join(''.join(row) for row in rows)
    
    def convert1(s, numRows):
        if numRows<2 or len(s)<numRows: return s
        n = numRows-1
        step = n*2
        res = s[::step]
        for i in range(1,n):
            for v,w in itertools.zip_longest(s[i::step],s[step-i::step],fillvalue=''):
                res += v+w
        return res + s[n::step]
    

    got below results

    >>> s, numRows = "wkpacxzafxqkxsvmjqeadpbmvbtbupgsbysdvtecqwmqqiecaicdyervhkyebhwcfricmofdmttddxfehjhhnbdxnbbp", 3
    >>> timeit('convert(s,numRows)', 'from __main__ import convert,s,numRows')
    19.997443535110506
    
    >>> timeit('convert2(s,numRows)', 'from __main__ import convert2,s,numRows')
    22.723585619482037
    
    >>> timeit('convert1(s,numRows)', 'from __main__ import convert1,s,numRows')
    5.070375056522607

  • 0
    L

    Great idea!!!!


  • 0
    E

    @qeatzy Great idea using zip_longest!

    My solution looked very similar, but with a while loop instead. Also I put 2 extra base cases hoping to get a bit of optimization in there

    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        length = len(s)
        if numRows == 1 or length <= numRows:
            return s
            
        if numRows == 2:
            return s[::2] + s[1::2]
            
        if numRows == 3:
            return s[::4] + s[1::2] + s[2::4]
            
        dist = 2 * numRows - 2
        start = s[::dist]
        end = s[numRows-1::dist]
        middle = ""
        for i in range(1, numRows - 1):
            j = i
            d2 = 2 * i
            d1 = dist - d2
            while j < length:
                middle += s[j]
                j += d1
                d1, d2 = d2, d1
        
        return start + middle + end

  • 0
    T

    I think use list instead of str will be faster, I test it and the result support.

    class Solution(object):
    def convert(self, s, numRows):
    """
    :type s: str
    :type numRows: int
    :rtype: str
    """
    if len(s) <= numRows or numRows == 1:
    return s
    L = []
    for i in range(numRows):
    L.append([])

        index = 0
        for ch in s:
            L[index].append(ch)
            if index == 0:
                step = 1
            if index == numRows - 1:
                step = -1
            index += step
            
        return ''.join([''.join(item) for item in L])

  • 0
    J

    能给点解释么 你这样谁看的懂


  • 0
    D

    @jz678 再仔细看两遍就理解了


  • 0
    S

    @DazzlingHelios cool!!!!!!!!!!


  • 0
    N

    brilliant!!!


  • 0
    B

    @DazzlingHelios Bravo!!


  • 0
    L

    @jz678 手动模拟一边就知道了~


  • 0
    L

    cool~ thanks


  • 0
    L

    @jz678 这题和zigzag一点关系都没有 直接把空格去掉反而好懂很多


  • 0
    Z
    This post is deleted!

Log in to reply
 

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