LeetCode 题解

积跬步，至千里。

Z 字形变换

分类：LeetCode 标签： 字符串 发布于：2019-10-20 ID：6

题目描述

来源于 https://leetcode-cn.com/

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

解法 1

顺序地遍历每个字符，然后判断该字符应该放在哪一行。可以在迭代的过程中维护一个行指针，该指针用于指出当前字符应该放在哪一行。这个指针在 0 到 num_rows 之间往返。

class Solution:
    def convert(self, s, num_rows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if num_rows == 1:
            return s

        rows = [''] * num_rows
        row_index = 0
        direction = 1

        for c in s:
            rows[row_index] += c

            if row_index == num_rows - 1:
                direction = -1
            elif row_index == 0:
                direction = 1

            row_index += direction

        return ''.join(rows)

解法 2

如果仔细分析每一行的各个字符在字符串中的下标，是能够发现规律的。这里不再尝试该方法了。详见Solution。