[LeetCode解題攻略] 6. Zigzag Conversion

這篇部落格文章將詳細解析 LeetCode 題目 6. Zigzag Conversion。這是一道字串操作題，要求將字串以 "Z" 字形排列，再按行讀取形成新的字串。以下是此題的詳細思路和解法，幫助你有效掌握此類問題。

題目概述

題目要求給定一個字串 s 和一個整數 numRows，將字串 s 按照 Z 字形排列，然後從上到下逐行讀取，以得到最終轉換的結果。

範例：

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

我們可以將字串 "PAYPALISHIRING" 按照以下方式以 Z 字形排列：

對於 numRows = 3：

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

對於 numRows = 4：

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

最後逐行讀取即可得到結果字串。

思路與解法

這道題的核心是將字串根據 Z 字形的模式填入不同的行，並按順序讀取。以下介紹兩種解法：

1. 模擬行走 Z 字形
2. 直接計算索引

解法一：模擬行走 Z 字形

這是最直觀的方法，我們可以將每一行分別視為一個字串。接著，依次遍歷 s 的字符，把它們按 Z 字形填入每行。

步驟：

1. 如果 numRows 是 1，直接返回原字串，因為無需轉換。
2. 建立一個包含 numRows 個空字串的列表 rows。
3. 使用變數 current_row 追踪當前行，布林變數 going_down 控制方向。
4. 當到達頂部或底部時，反向改變行進方向。
5. 最後，把 rows 中的內容連接成新字串，作為結果。

實作 (Python)：

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

        rows = [''] * numRows
        current_row, going_down = 0, False

        for char in s:
            rows[current_row] += char
            if current_row == 0 or current_row == numRows - 1:
                going_down = not going_down
            current_row += 1 if going_down else -1

        return ''.join(rows)

複雜度分析：

• 時間複雜度：O(n)，其中 n 是字串長度，因為我們需要遍歷每個字符。
• 空間複雜度：O(n)，儲存每一行的字串。

這是性能不錯且易於理解的解法，適合大多數情況。

解法二：直接計算索引

這個方法觀察到 Z 字形排列有一定的周期性，如果 numRows 為 3，則週期為 4。依此規律，可以直接將字符放到相應的位置，省去逐行遍歷的過程。

思路

1. Z 字形排列的模式具有週期性。假設 numRows = 3，則每 4 個字符為一個完整的 Z 字形。
2. 可以分成「垂直向下填充」和「向上斜線填充」兩種模式：
3. • 垂直向下填充：先從上往下填滿每行。
   • 向上斜線填充：然後從底部向上填一行，直到頂部。
3. 如果 numRows 是 1 或 numRows 大於字串長度，我們可以直接返回原字串，因為它無需變換。

實作 (Python)：

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        
        # 定義每行的容器
        rows = [''] * numRows
        n = len(s)
        cycle_len = 2 * numRows - 2  # 每個 Z 字形週期長度

        for i in range(n):
            cycle_pos = i % cycle_len
            if cycle_pos < numRows:
                # 垂直向下填充
                rows[cycle_pos] += s[i]
            else:
                # 斜線向上填充
                rows[cycle_len - cycle_pos] += s[i]

        # 將所有行合併
        return ''.join(rows)

複雜度分析

• 時間複雜度：O(n)，其中 n 是字串長度，因為我們需要遍歷每個字符。
• 空間複雜度：O(n)，因為我們使用了額外的空間來儲存每行的字串內容。

總結

這道題是字串操作與數學規律結合的典型問題。以下是不同解法的適用情境：

• 模擬行走 Z 字形：簡單直觀，適合大多數場景。
• 直接計算索引：進階解法，適合需要減少空間使用的情況。

希望這篇解題教學能幫助你輕鬆掌握 Zigzag Conversion 的解法！