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

• ``````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)``````

• 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)``````

• Good idea! Thanks

• cool!.......................................

• 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``````

• Great idea!!!!

• @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``````

• 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])``````

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

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

• @DazzlingHelios cool！！！！！！！！！！

• brilliant!!!

• @DazzlingHelios Bravo!!

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

• cool~ thanks

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

• This post is deleted!

• That's awesome you are a genius， thanks for sharing

• @DazzlingHelios So brilliant

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