LeetCode 6. Z 字形變換：雙指針模擬遍歷 O(n) 時間 O(n) 空間優雅解法

LeetCode 6. Z 字形變換：雙指針模擬遍歷 O(n) 時間 O(n) 空間優雅解法

題目：將字符串按 Z 字形（N 行）排列後按行讀取生成新字符串。
難度：Easy
示例："PAYPALISHIRING", 3 行 → "PAHNAPLSIIGYIR"

核心規律洞察

週期性結構

Z 字形軌跡呈現固定週期：下行 → 右上斜行 → 下行 → ...
週期長度 cycle = 2 * (numRows - 1)（首尾行無斜行部分）。

行索引計算公式

• 第 0 行：索引 0, cycle, 2*cycle, ... → 間隔 cycle
• 第 numRows-1 行：索引 numRows-1, numRows-1+cycle, ... → 間隔 cycle
• 中間行 i：兩個間隔交替出現
  • 向下間隔：down = 2 * (numRows - 1 - i)
  • 向上間隔：up = 2 * i

優雅 Java 實現（單次遍歷，無額外數組）

class Solution {
    public String convert(String s, int numRows) {
        if (numRows <= 1 || s.length() <= numRows) return s;
        
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        int cycle = 2 * (numRows - 1);
        
        for (int row = 0; row < numRows; row++) {
            int down = 2 * (numRows - 1 - row);
            int up = 2 * row;
            boolean goDown = true; // 方向標誌
            
            for (int i = row; i < n; ) {
                sb.append(s.charAt(i));
                
                if (row == 0 || row == numRows - 1) {
                    i += cycle; // 首尾行固定間隔
                } else {
                    i += goDown ? down : up; // 中間行交替間隔
                    goDown = !goDown;        // 翻轉方向
                }
            }
        }
        return sb.toString();
    }
}

關鍵細節解析

複雜度分析

• 時間 O(n)：每個字符恰好被訪問並追加一次
• 空間 O(n)：StringBuilder 存儲結果，輸出必然佔用

對比：矩陣模擬法（直觀但低效）

// 缺點：O(n * numRows) 空間，需遍歷矩陣讀取，邊界判斷繁瑣
char[][] matrix = new char[numRows][n];
int row = 0, col = 0, dir = 1; // 1向下, -1向上
for (char c : s.toCharArray()) {
    matrix[row][col++] = c;
    if (row == 0) dir = 1;
    else if (row == numRows - 1) dir = -1;
    row += dir;
}
// 再按行讀取非空字符...

測試用例驗證

@Test
public void test() {
    Solution sol = new Solution();
    assertEquals("PAHNAPLSIIGYIR", sol.convert("PAYPALISHIRING", 3));
    assertEquals("PINALSIGYAHRPI", sol.convert("PAYPALISHIRING", 4));
    assertEquals("A", sol.convert("A", 1));
    assertEquals("ABCD", sol.convert("ABCD", 5)); // 行數超長度
    assertEquals("AB", sol.convert("AB", 1));
}

擴展思考：流式處理超長字符串

若字符串極長（GB 級），可改為生成器模式逐行輸出，避免全量內存佔用：

public Stream convertStream(Reader reader, int numRows) {
    // 使用環形緩衝區或臨時文件分行緩存，逐行 yield
    // 核心索引計算邏輯不變，僅將 sb.append 改為寫入行緩衝
}

「Z 字形變換本質是週期性索引映射問題。掌握『首尾固定間隔、中間交替間隔』規律，即可用 O(1) 額外空間（不計輸出）單趟掃描解決，這是字符串模擬類題目的通用解題模板。」