LeetCode Z 字形變換：行索引數學規律 O(n)

題目描述

將字符串按 Z 字形（鋸齒形）排列在 nRows 行，然後按行讀取生成新字符串。

範例：

輸入: "PAYPALISHIRING", nRows = 3
排列:
P   A   H   N
A P L S I I G
Y   I   R
輸出: "PAHNAPLSIIGYIR"

解題思路：索引周期律

觀察規律，定義 Step = 2 * nRows - 2（一個完整 V 字週期）：

• 第 0 行、第 nRows-1 行：索引為 i, i+Step, i+2*Step, ...
• 中間行 i：雙序列交替 i, Step-i, i+Step, 2*Step-i, ...

直接按規律收集字符，無需模擬二維排列。

時間複雜度：O(n)，空間複雜度：O(n)。

C++ 參考實現

class Solution {
public:
    std::string convert(std::string s, int nRows) {
        int len = s.size();
        if (len <= nRows || nRows == 1) return s;
        
        int step = 2 * nRows - 2;
        std::string result;
        result.reserve(len);
        
        for (int row = 0; row < nRows; ++row) {
            int idx1 = row;
            int idx2 = step - row;  // 第二序列起始
            
            if (row == 0 || row == nRows - 1) {
                // 首尾行：單序列
                while (idx1 < len) {
                    result.push_back(s[idx1]);
                    idx1 += step;
                }
            } else {
                // 中間行：雙序列交替
                while (idx1 < len || idx2 < len) {
                    if (idx1 < len) {
                        result.push_back(s[idx1]);
                        idx1 += step;
                    }
                    if (idx2 < len) {
                        result.push_back(s[idx2]);
                        idx2 += step;
                    }
                }
            }
        }
        return result;
    }
};

核心要點總結

• 數學建模：將幾何排列轉化為索引算術序列
• 週期 Step：2*nRows-2 是核心參數，首尾行步長 Step，中間行雙序列
• 邊界處理：nRows=1 或 len<=nRows 直接返回原串
• 空間預留：result.reserve(len) 避免多次擴容

Z 字形變換通過發現「索引周期律」將 O(n²) 模擬降為 O(n) 直接構造，是「找規律優化算法」的典型範例。