LeetCode 6. Z 字形变换 | 详细题解（附 C++ 代码）

一、题目描述

题目链接：LeetCode 6. Z 字形变换

题目要求

将字符串s按指定行数numRows排成Z 字形（先从上到下，再从右到左斜向上），然后从左到右逐行读取，输出新字符串。

示例演示

• 输入：s = "PAYPALISHIRING", numRows = 3
• Z 字形排列：

plaintext

P A H N A P L S I I G Y I R

• 输出："PAHNAPLSIIGYIR"

二、解题思路：Z 字的 “周期” 与 “方向”

要解决这道题，首先得搞懂 Z 字形的排列规律：

1. 周期规律

Z 字形的每一个 “完整折回” 是一个周期，周期长度为：t=2×numRows−2（比如numRows=3时，周期t=4：向下 3 个字符 + 斜向上 2 个字符）

2. 方向切换

在一个周期内，字符的移动方向分两种：

• 前numRows-1个字符：垂直向下（行 + 1）；
• 后numRows-2个字符：斜向上（行 - 1，列 + 1）。

3. 核心解题步骤

我们用模拟矩阵法实现（直观易懂）：

1. 处理特殊情况（行数为 1 / 行数≥字符串长度）；
2. 计算周期和矩阵的行列数；
3. 模拟 Z 字路径，将字符填充到矩阵中；
4. 逐行读取矩阵，拼接成结果字符串。

三、图解过程（以示例 1 为例）

以s="PAYPALISHIRING", numRows=3为例：

步骤 1：计算周期和矩阵大小

• 周期t=2×3-2=4；
• 字符串长度n=14，总周期数为(14+4-1)/4=4（向上取整）；
• 矩阵列数c=4×(3-1)=8（每个周期占 2 列）。

步骤 2：填充矩阵

遍历字符串，按方向填充字符：

• 第 1 个字符P：坐标 (0,0)，向下移动→行 + 1；
• 第 2 个字符A：坐标 (1,0)，向下移动→行 + 1；
• 第 3 个字符Y：坐标 (2,0)，进入周期后半段→斜向上（行 - 1，列 + 1）；
• 第 4 个字符P：坐标 (1,1)，斜向上→行 - 1，列 + 1；
• 以此类推，直到填充完所有字符。

步骤 3：逐行读取

矩阵填充完成后，逐行拼接非空字符：

• 第 0 行：P A H N→ 拼接为PAHN；
• 第 1 行：A P L S I I G→ 拼接为APLSIIG；
• 第 2 行：Y I R→ 拼接为YIR；
• 最终结果：PAHNAPLSIIGYIR。

四、代码细节说明

1. 特殊情况处理：当行数为 1 时，Z 字就是原字符串；当行数≥字符串长度时，无法形成 Z 字，直接返回原串。

2. 矩阵大小计算：

   • 周期t：Z 字每 “一折” 的字符数；
   • 列数c：通过 “向上取整” 计算总周期数，再乘以每个周期的列数r-1。

3. 方向控制：用i % t判断当前字符在周期中的位置：

   • i%t < r-1：周期前半段，向下移动（行 + 1）；
   • 否则：周期后半段，斜向上移动（行 - 1，列 + 1）。

五、复杂度分析

• 时间复杂度：O(r×c)填充矩阵和拼接结果的时间，r是行数，c是列数，均与字符串长度呈线性关系。
• 空间复杂度：O(r×c)存储矩阵的空间，可优化为O(n)（直接按行存储字符，无需完整矩阵）。

六、优化思路（空间 O (n)）

如果想优化空间，可放弃完整矩阵构建，直接按行存储字符：

• 定义行数对应的字符串数组，遍历原字符串时直接将字符追加到对应行；
• 到达行首 / 行尾时切换移动方向，避免矩阵的空间浪费；
• 最终将各行字符串拼接即可得到结果，空间复杂度可降至O(n)。