问题描述
字符串 "PAYPALISHIRING" 写成指定行数的 zigzag 模式如下，它很像一个字符串在走 Z 字形:
P A H N
A P L S I I G
Y I R
将其每行字符串再连起来："PAHNAPLSIIGYIR"
实现函数，输入一个字符串和一个行号，返回上述转换后的字符串
string convert(string s, int numRows);
例 1:
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"
例 2:
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
解释:
P I N
A L S I G
Y A H R
P I
问题难度
Medium
解题思路
这道题虽然是中等难度，但实际上解起来很简单，按题目要求，需要把原字符串按一定规则拆成 n 个子字符串，再将这 n 个子字符串首尾相连即可。
接下来就是如何拆原字符串的问题了，直接看上面的例子也许更容易些
原字符串: PAYPALISHIRING
行数: 4
拆分结果:
[0]: P I N
[1]: A L S I G
[2]: Y A H R
[3]: P I
上面的 4 个子字符串分别用序号 0-4 表示，接下来我们再把该序号标记到到原字符串中，每个字符对应一个序号
PAYPALISHIRING
01232101232101
发现规律了吧，于是我们可以写一个程序，为原字符串中的每个字符标记其所属的子字符串的序号，然后再根据该序号来构建 n 个子字符串，最后将它们按照升序的顺序首位相连。
这样做的时间复杂度和空间复杂度都是 O(n)，代码如下：
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
index = 0
sign = 1
zigzag_array = []
for c in s:
if index == 0:
sign = 1
elif index == numRows - 1:
sign = -1
if len(zigzag_array) < index + 1:
zigzag_array.append("")
zigzag_array[index] += c
index += sign
return "".join(zigzag_array)
