LeetCode 6 ZigZag Conversion：Z 字形變換的直觀解法

題目大意

將字符串按 Z 字形（鋸齒形）排列在 numRows 行，然後按行讀取生成新字符串。
例："PAYPALISHIRING", numRows = 3 →

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

輸出："PAHNAPLSIIGYIR"。

核心思路：模擬行緩衝區

不必建立二維數組，只需維護 numRows 個 StringBuilder（或字符串列表），模擬「向下 → 向右上 → 向下」的走向，將字符依次追加到對應行的緩衝區。最後拼接所有行即可。

算法步驟

1. 邊界情況：numRows == 1 或 s.length() <= numRows 直接返回原串。
2. 創建 rows[numRows] 字符串緩衝區。
3. curRow = 0, goingDown = false。
4. 遍歷字符 c：
   • 追加到 rows[curRow]。
   • 若 curRow == 0 || curRow == numRows-1，翻轉 goingDown。
   • curRow += goingDown ? 1 : -1。
5. 拼接 rows[0] + ... + rows[numRows-1] 返回。

Java 實現

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) return s;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; ++i) rows[i] = new StringBuilder();
        int curRow = 0;
        boolean down = false;
        for (char c : s.toCharArray()) {
            rows[curRow].append(c);
            if (curRow == 0 || curRow == numRows - 1) down = !down;
            curRow += down ? 1 : -1;
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder row : rows) res.append(row);
        return res.toString();
    }
}

Python 實現

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        rows = [''] * 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)

複雜度分析

• 時間：O(n)，單次遍歷字符串。
• 空間：O(n)，存儲所有字符。

總結

關鍵在於拋棄二維坐標思維，改用「行緩衝區 + 方向標誌」模擬走向。這是字符串模擬類問題的通用技巧：用一維數組模擬二維軌跡。