LeetCode 經典題目：ZigZag Conversion 鋸齒轉換完整解析

題目簡介

ZigZag Conversion 是 LeetCode 上一道經典的字符串操作題目。給定一個字符串和指定的行數，將字符串以「Z」字形（鋸齒狀）排列後，再按行讀取生成新字符串。例如輸入 PAYPALISHIRING、行數 3，排列如下：

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

按行讀取得到 PAHNAPLSIIGYIR。需要實現函數 string convert(string text, int nRows)。

核心思路：數學規律推導

關鍵在於找出原字符串下標與鋸齒排列後位置的映射關係。設行數為 nRows，定義週期 Step = 2 * nRows - 2。觀察可發現：

• 首行（第 0 行）與尾行（第 nRows-1 行）：元素下標為 i, i+Step, i+2*Step…
• 中間行：每行包含兩個交替序列：i, Step-i, i+Step, 2*Step-i…

掌握此規律後，只需按行遍歷收集字符即可，時間複雜度 O(n)，空間複雜度 O(n)。

完整實現代碼 (C++)

class Solution {
public:
    string convert(string s, int nRows) {
        const int Size = s.size();
        if ((Size <= nRows) || (nRows == 1)) return s;
        const int Step = 2 * nRows - 2;
        string Result;
        for (int RowIndex = 0; RowIndex < nRows; RowIndex++) {
            int Index = RowIndex;
            if ((RowIndex == 0) || (RowIndex == (nRows - 1))) {
                while (Index < Size) {
                    Result.push_back(s[Index]);
                    Index += Step;
                }
                continue;
            }
            int SecondIndex = Step - Index;
            while ((Index < Size) || (SecondIndex < Size)) {
                if (Index < Size) {
                    Result.push_back(s[Index]);
                    Index += Step;
                }
                if (SecondIndex < Size) {
                    Result.push_back(s[SecondIndex]);
                    SecondIndex += Step;
                }
            }
        }
        return Result;
    }
};

圖解示例

圖中展示了下標 0~12 在 3、4、5 行時的鋸齒分布，直觀對應上述數學規律。

解題心得

本題核心在於「找規律」：將原有序下標數組按特定映射亂序。畫圖輔助分析是解決此類問題的有效手段。掌握首尾行與中間行的差異處理，即可輕鬆實現線性掃描算法。