6. Zigzag Conversion

📘 題目敘述

字串 s 會以 numRows 行的 Zigzag 方式排列，然後再依照每一行由上到下讀出，形成新的字串。

請回傳 Zigzag 轉換後的字串。

條件限制

• 1 ≤ s.length ≤ 1000
• s 由英文字母（小寫與大寫）、,、. 組成
• 1 ≤ numRows ≤ 1000

🧠 解題思路

我的想法是：不要真的把 Zigzag 畫成矩陣，而是直接找出「每一行在原字串 s 裡會被讀到的索引位置」，依序把字元接到答案字串 zig。

Zigzag 排列有一個固定的週期（cycle）：

• cycle = numRows - 1
• 每一次完整的「往下 + 往上」會回到同一行
• 對應到索引跳躍的總距離是 cycle * 2

因此我用「逐行掃描」的方式：

1. 外層用 i 代表目前要處理第 i 行
2. 內層用 count 代表在原字串中下一個要取的索引
3. 每行依照規則更新 count，直到超出 s.size() 為止

所有變數（對應程式碼）

• zig：最後要回傳的結果字串（依照 Zigzag 讀行順序拼起來）
• cycle：numRows - 1，用來計算每次索引跳躍的週期
• i：目前正在處理的行數（從 0 到 numRows - 1）
• count：目前在原字串 s 中要讀取的索引位置

🪜 主要流程步驟

步驟一：特判 numRows == 1

• 如果 numRows == 1，Zigzag 其實不會改變排列
• 直接回傳原字串 s

步驟二：逐行讀取字元（外層 for）

• 外層 for (int i = 0; i < numRows; i++)：
  • 表示我會照「第 0 行 → 第 1 行 → ... → 第 numRows-1 行」依序把該行的字元放進 zig

步驟三：在同一行內，依規則跳索引（內層 while）

每一行會從 count = i 開始：

• count 表示目前要讀的字元是 s[count]
• 只要 count < s.size() 就持續往後取字元

情況一：第一行 / 最後一行（i == 0 或 i == cycle）

• 這兩行在 Zigzag 中沒有「斜上」的字元
• 所以同一行內的索引都是固定跳 cycle * 2

也就是每輪都做：

• 取 s[count]
• count += cycle * 2

情況二：中間行（其他的 i）

中間行會出現「兩種不同間距」交替：

• 第一個間距：(numRows - 1) * 2 - 2 * i
• 第二個間距：2 * i

我的做法是：

1. 先取 s[count]
2. 用第一個間距更新 count，並嘗試再取一次（對應到斜上那個字）
3. 再用第二個間距更新 count，回到下一個週期的位置

這樣就能在不建表的情況下，把中間行該出現的字元依序抓出來。

💻 程式碼實作

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        string zig = "";
        int cycle = numRows - 1;
        for (int i = 0; i < numRows; i++) {
            int count = i;
            while (count < s.size()) {
                zig = zig + s[count];
                if (i == 0 || i == cycle) {
                    count = count + cycle * 2;
                } else {
                    count = count + (numRows - 1) * 2 - 2 * i;
                    if (count < s.size()) {
                        zig = zig + s[count];
                    } else {
                        break;
                    }
                    count = count + 2 * i;
                }
            }
        }
        return zig;
    }
};

🔗 題目連結

https://leetcode.com/problems/zigzag-conversion/