The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
image.png
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR"
Solution
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 = [''] * numRows
index = 0
step = 1
for i in s:
l[index] += i
if index >= numRows - 1:
step = -1
elif index <= 0:
step = 1
index += step
return "".join(l)
思路
- 首先，要想到结果是一个numRows个元素的list，然后将list中的每个元素相加起来显示即可
- 先观察第一列的值，基本的步骤是在遍历字符串的过程中，会将相应的字符置放在list中相应的位置。list的index有时候是+1，有时候是-1，需要有逻辑进行控制。
反思
- 解题过程中，想到了用递归来生成每个之形结果，但是递归的结束条件不好找，字符的index跟list的index不好有一个对应关系
- 递归结果会将整个问题变得更加复杂
- 回过头来看proposal，这种做法简单、自然
