LeetCode 6. Z 字形变换

◎

本节目标

用当前行和移动方向模拟字符在多行之间的往返轨迹。

这道题是字符串综合中的方向状态母题。字符沿行向下移动，到达末行后再向上移动；最终答案不是原来的访问顺序，而是把各行依次拼接。

查看原题

题意与约束

给定字符串 s 和行数 numRows，按照向下、再斜向上的往返轨迹排列字符，返回逐行读取后的新字符串。

当行数为一，或行数不少于字符数时，所有字符都不会形成真正的折返，可以直接返回原串。

从坐标公式转向状态模拟

可以推导每个字符在一个周期中的行号，但周期公式需要分别处理首尾行和中间行。更直接的办法是保存：

• row：当前字符写入哪一行；
• direction：下一步向下 +1 还是向上 -1。

每写入一个字符，只在 row == 0 或 row == numRows - 1 时更新方向，然后移动到下一行。

边界为什么必须先处理

若 numRows == 1，首行同时也是末行。继续执行方向模拟会让 row 离开唯一合法下标。把退化情况提前返回，不仅避免越界，也让主循环只处理确实存在上下边界的情形。

代码实现

C++ 使用字符串作为行缓冲，Python 使用可变字符列表。扫描过程中每个字符只写入一次；扫描结束后，Python 先逐行 join，再把各行整体连接。

C++

C++17

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1 || numRows >= static_cast<int>(s.size())) {
            return s;
        }

        vector<string> rows(numRows);
        int row = 0;
        int direction = 1;

        for (char ch : s) {
            rows[row] += ch;
            if (row == 0) {
                direction = 1;
            } else if (row == numRows - 1) {
                direction = -1;
            }
            row += direction;
        }

        string answer;
        for (const string& current : rows) {
            answer += current;
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s

        rows = [[] for _ in range(numRows)]
        row = 0
        direction = 1

        for ch in s:
            rows[row].append(ch)
            if row == 0:
                direction = 1
            elif row == numRows - 1:
                direction = -1
            row += direction

        return "".join("".join(row) for row in rows)

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度。
• 空间复杂度：O(n)，行缓冲区合计保存全部字符。

易错点

• 忘记单行和行数不少于字符串长度的退化情况。
• 在写入边界字符前切换方向，使字符落入错误行。
• 把方向理解成字符在平面中的横纵坐标，维护了不需要的列信息。

模式迁移

凡是状态在两个边界之间往返，都可以用“当前位置＋方向”描述，例如蛇形打印、双向扫描动画和周期性折返模拟。先确定何时改变方向，再让主循环只负责一次移动。