LeetCode 6 ZigZag Conversion

一、题目链接

https://leetcode.com/problems/zigzag-conversion/

二、解答

这题有多个解答，我只取一种比较直观的，而且我认为，这种解法是最适合计算机的，其他如找出数学规律的解答，其数学思想是好的，但是，我认为利用直观的解法可以节约我们的时间。

先给出代码

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2:
            return s
        row_strs = []
        for i in range(numRows):
            row_strs.append('')
        row = 0
        flag = -1
        for i in range(len(s)):
            row_strs[row] += s[i]
            if row == 0 or row == numRows - 1:
                flag = -flag
            row += flag
        ans = ''
        for each in row_strs:
            ans += each
        return ans

本题的解法思路很明显，我们把每一行当成一个子串单独拎出来，然后，根据 ZigZag 的规律直接一个一个往各层的子串中添加字符即可。顺着那个 ZigZag 的轨迹来，可以说是比较直观的。这里比较机智的一个点是使用 flag 标志来控制拉链形的轨迹。

时间复杂度：$O(N)$。 空间复杂度：$O(N)$。

三、完整代码

# -*- coding: utf-8 -*-
# @File  : leet_06.py
# @Author: FanyFull
# @Date  : 2021/7/11

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2:
            return s
        row_strs = []
        for i in range(numRows):
            row_strs.append('')
        row = 0
        flag = -1
        for i in range(len(s)):
            row_strs[row] += s[i]
            if row == 0 or row == numRows - 1:
                flag = -flag
            row += flag
        ans = ''
        for each in row_strs:
            ans += each
        return ans

if __name__ == '__main__':
    solution = Solution()
    s = 'AB'
    numRows = 1
    ans = solution.convert(s, numRows)
    print(ans)