題目描述:將字串 s 按照鋸齒形(Zigzag)排列在 numRows 列上,然後逐列從左到右讀取所有字元,回傳讀取結果。例如字串 "PAYPALISHIRING" 在 3 列時排列如下:
P A H N
A P L S I I G
Y I R
逐列讀取得到 "PAHNAPLSIIGYIR"。
解題思路:模擬法(Simulation) — 直接模擬字元被放入哪一列。
建立 numRows 個字串 rows[0..numRows-1],用一個變數 curRow 記錄目前填入的列,用一個布林值 goingDown 記錄移動方向。
遍歷字串 s 中的每個字元,將其附加到 rows[curRow]。然後更新 curRow:
curRow == 0,方向改為向下(goingDown = true)curRow == numRows - 1,方向改為向上(goingDown = false)curRow 加 1 或減 1最後將所有列的字串依序拼接,即為答案。
特別注意:若 numRows == 1,直接回傳原字串(只有一列,Zigzag 沒有意義)。
時間複雜度:O(n) — 遍歷字串 s 一次(n 個字元),最後拼接所有列的字串也是 O(n),整體線性時間。
空間複雜度:O(n) — rows 陣列中共儲存 n 個字元,加上結果字串,額外空間為 O(n)。若不計輸出字串,模擬所需的 rows 陣列仍需 O(n) 空間。
1. If numRows == 1 or numRows >= len(s), return s directly. 2. Create rows[0..numRows-1] as empty strings. 3. Set curRow = 0, goingDown = false. 4. For each character c in s: a. Append c to rows[curRow]. b. If curRow == 0 or curRow == numRows-1, flip goingDown. c. curRow += (goingDown ? 1 : -1). 5. Concatenate all rows[0], rows[1], ..., rows[numRows-1]. 6. Return the concatenated string.
方法一:模擬法(本題主解法)
如上所述,用 numRows 個字串緩衝區模擬填入過程,配合方向旗標來回彈跳。時間 O(n),空間 O(n),邏輯直觀,是最推薦的寫法。
方法二:數學規律(按行計算字元索引)
觀察每一列的字元在原字串中的索引規律:設週期 cycle = 2 * (numRows - 1)。第 0 列和第 numRows-1 列每個 cycle 只有一個字元;中間第 r 列每個 cycle 有兩個字元,索引分別為 k * cycle + r 和 (k+1) * cycle - r。按此規律直接構造答案,無需模擬移動過程。時間 O(n),空間 O(n)(輸出),不需要額外的 rows 陣列,但需要數學推導,較難直接記憶。
方法三:暴力構造二維矩陣 真的建立一個二維字元矩陣,按 Zigzag 模式填入字元,再逐列讀取。時間 O(n),空間 O(numRows × cols),浪費大量空間(矩陣中大部分位置為空),實用性低。
numRows 非常大(例如大於字串長度),程式應如何處理以避免建立不必要的空列?本解法是否已處理這種邊界情況?numRows,還原出原始字串,應如何設計演算法?