這篇部落格文章將詳細解析 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 字形的模式填入不同的行，並按順序讀取。以下介紹兩種解法：
- 模擬行走 Z 字形
- 直接計算索引
解法一：模擬行走 Z 字形
這是最直觀的方法，我們可以將每一行分別視為一個字串。接著，依次遍歷 s 的字符，把它們按 Z 字形填入每行。
步驟：
- 如果
numRows是 1，直接返回原字串，因為無需轉換。 - 建立一個包含
numRows個空字串的列表rows。 - 使用變數
current_row追踪當前行，布林變數going_down控制方向。 - 當到達頂部或底部時，反向改變行進方向。
- 最後，把
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。依此規律，可以直接將字符放到相應的位置，省去逐行遍歷的過程。
思路
- Z 字形排列的模式具有週期性。假設
numRows = 3，則每 4 個字符為一個完整的 Z 字形。 - 可以分成「垂直向下填充」和「向上斜線填充」兩種模式：
- 垂直向下填充：先從上往下填滿每行。
- 向上斜線填充：然後從底部向上填一行，直到頂部。
- 如果
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 的解法！
