锯齿转换

题目

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

给出的字符串是 "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”

分析

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

  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条规律即可解题

解题

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的社区中看到了跟我思路相同的解法，但人家的代码更简洁，主要是利用了字符串的特性，减少了数组的拼接。

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)