锯齿转换

题目

给出一个字符串s和要求的输出的行数numRow,求锯齿转换后按行读取的结果。
比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
给出的字符串是 "PAYPALISHIRING" ,分3行

P A H N
A P L S I I G
Y I R
按行读取的结果是 : "PAHNAPLSIIGYIR"

如果函数为4,

P I N
A L S I G
Y A H R
P I

输出: “PINALSIGYAHRPI”

分析

第一直觉是要利用二维数据,每一行为一个子数组,根据锯齿的特性,依次往每个数组里填充元素,直至完成。
给每个行和列标注坐标以后:

1
2
3
4
5
  0 1 2 3 4 5 6
0 P I N
1 A L S I G
2 Y A H R
3 P I

得出如下的规律:

  1. 字符串的每个坐标位置index与列col和行row存在关系: 2col + row = index
  2. 当row增长到numRow大小时,开始递减,并递减至0时开始递增。

仅借用第2条规律即可解题

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
# res = [[]] * numRows
if numRows ==1:
return s
res = [[] for i in range(numRows)]
flag,row = 1,0

for index in range(len(s)):
res[row].append(s[index])
if row == numRows-1:
flag =-1
if row ==0:
flag =1
row += flag

rs = ''
for ar in res:
rs +=''.join(ar)
return rs

该解法只遍历了一遍字符串,因此时间复杂度为O(n)。

跳坑总结

第一次写代码时,想构建一个二维数组,写成了[[]]* numRow. 运行时发现不正确,这里时一处坑。

代码的优化

leetcode的社区中看到了跟我思路相同的解法,但人家的代码更简洁,主要是利用了字符串的特性,减少了数组的拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)
你的支持我的动力