Z 字形变换 图解题解

这道题到底在问什么

s

"PAYPALISHIRING"

numRows

3

输出

"PAHNAPLSIIGYIR"

最优解：一步一步想明白

1. 3关键就两个状态:当前行 cur 和 方向 step(+1 往下 / −1 往上)。碰到顶行或底行就掉头。盯住下面格子里字母怎么走位。
2. 4cur=0 · 准备填 P先摆好 3 行的空格子(列数够用就行)。指针停在 第 0 行,方向往下,准备填第一个字母 P。
3. 5cur=0 → 往下把 P 放进 (行0, 列0)。现在在顶行,方向是往下 +1,下一格去第 1 行。
4. 6往下 · cur 0→1竖着往下,A 放进 (行1, 列0)。还没到底,继续往下。
5. 7撞底 → 准备掉头Y 放进 (行2, 列0)——到最后一行了!方向要掉头变成往上 −1,而且斜着走时列要 +1。
6. 8往上 · 列+1掉头往上!P 走到 (行1, 列1)——行号减 1、列号加 1,这就是 Z 字的斜笔。
7. 9撞顶 → 再掉头A 走到 (行0, 列2)——又撞到顶行了!方向再掉头变回往下 +1,接下来又是竖着走。
8. 10往下 · cur 0→1竖着往下,L 放进 (行1, 列2)。注意列号不变——竖着走时同一列往下叠。
9. 11撞底 → 掉头往上I 放进 (行2, 列2),又到底了。掉头往上,下一步斜着走、列再 +1。
10. 12往上 · 列+1斜笔!S 走到 (行1, 列3)。行减 1、列加 1。
11. 13撞顶 → 掉头往下H 走到 (行0, 列4),撞顶,再次掉头往下。Z 字就是这样一上一下来回织。
12. 14往下 · cur 0→1竖着往下,I 放进 (行1, 列4)。
13. 15撞底 → 掉头R 放进 (行2, 列4),到底,掉头往上。
14. 16往上 · 列+1斜笔,I 走到 (行1, 列5)。还剩两个字母 N、G。
15. 17撞顶 → 掉头往下N 走到 (行0, 列6),撞顶,掉头往下。
16. 18往下 · 填完!最后一个 G 往下放进 (行1, 列6)。14 个字母全部按 Z 字填完了!下面开始一行一行读出来。
17. 19全部填完 · 看整张 Z 字退一步看整张图:字母的轨迹正是一笔一笔的 Z 字(竖下→斜上→竖下…)。原串顺序已经被打散到各行,接下来从上到下逐行读出来就是答案。
18. 20row 0 → PAHN从第 0 行从左到右收字母:P、A、H、N → 拿到 "PAHN"。空格子直接跳过。
19. 21row 1 → APLSIIG再读第 1 行:A、P、L、S、I、I、G → 接上变成 "PAHN" + "APLSIIG"。中间行字母最多,因为斜笔都落在这。
20. 22row 2 → YIR · 完成最后读第 2 行:Y、I、R → 全拼起来 PAHN + APLSIIG + YIR = PAHNAPLSIIGYIR,正是答案!
21. 23省内存的写法:不存格子,只存 numRows 个行串。指针在行间来回走,字母追加到对应行串,走到顶/底就翻转方向。
22. 27只有 1 行 → 原样返回若 numRows=1,所有字母都挤在同一行,顶行就是底行、方向永远翻不过来。所以必须开头特判,直接原样返回 s(ABCDEF→ABCDEF)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def convert(self, s, numRows):
        if numRows == 1:
            return s                 # 一行不用变换
        rows = [''] * numRows         # numRows 个行串
        cur, step = 0, 1              # 当前行 / 方向
        for ch in s:
            rows[cur] += ch           # 追加到当前行
            if cur == 0:
                step = 1              # 顶行 → 往下
            elif cur == numRows - 1:
                step = -1             # 底行 → 往上
            cur += step
        return ''.join(rows)          # 逐行拼接

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> rows(numRows);
        int cur = 0, step = 1;
        for (char ch : s) {
            rows[cur] += ch;
            if (cur == 0) step = 1;
            else if (cur == numRows - 1) step = -1;
            cur += step;
        }
        string res;
        for (string& r : rows) res += r;
        return res;
    }
};

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
        int cur = 0, step = 1;
        for (int i = 0; i < s.length(); i++) {
            rows[cur].append(s.charAt(i));
            if (cur == 0) step = 1;
            else if (cur == numRows - 1) step = -1;
            cur += step;
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder r : rows) res.append(r);
        return res.toString();
    }
}

复杂度

面试官可能追问