6. Zigzag Conversion

題目 / Problem

中文： 將字串 s 以鋸齒形（zigzag）方式寫在 numRows 列上，然後一列一列地讀取，回傳結果字串。

例如 "PAYPALISHIRING"，numRows = 3 時排列如下：

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

一列一列讀取得到 "PAHNAPLSIIGYIR"。

請實作函式：

string convert(string s, int numRows);

English: Write the string s in a zigzag pattern on numRows rows, then read it line by line to produce the output.

For s = "PAYPALISHIRING", numRows = 3, the zigzag layout is shown above, and reading row by row gives "PAHNAPLSIIGYIR".

Constraints / 限制： - 1 <= s.length <= 1000 - s 由大小寫英文字母、','、'.' 組成 - 1 <= numRows <= 1000

Worked example / 範例： - Input: s = "PAYPALISHIRING", numRows = 4 - Output: "PINALSIGYAHRPI" - Layout: P I N A L S I G Y A H R P I

名詞解釋 / Glossary

• Zigzag pattern / 鋸齒形排列：字元先由上往下填入每一列，到最後一列後再斜向上回到第一列，如此循環。Characters fill rows top-down, then diagonally back up to the top, repeating.
• Row buffer / 列緩衝區：為每一列準備一個獨立的字串容器，用來收集屬於該列的字元，最後再依序串接起來。An independent string container for each row that collects its characters; concatenated at the end.
• Direction flag / 方向旗標：一個布林或整數值（例如 +1 / -1），用來記錄目前是「往下走」還是「往上走」，遇到頂列或底列時翻轉。A boolean/integer (+1 / -1) tracking whether we are moving down or up; flipped at the top or bottom row.
• Edge case / 邊界情況：輸入特別小或退化時的特殊處理，例如 numRows == 1 時根本沒有鋸齒，應直接回傳原字串。Special handling for degenerate inputs (e.g. numRows == 1 means no zigzag at all).
• malloc / free (C)：C 語言中向作業系統申請與釋放動態記憶體的函式。LeetCode 的 C 題目通常要求回傳 malloc 出來的字串。Standard C calls to dynamically allocate / release heap memory; LeetCode C problems usually expect a malloc-returned string.
• std::string / std::vector (C++)：C++ 標準函式庫中的可變長度字串與動態陣列，會自動管理記憶體。C++ standard-library types for resizable strings and arrays that manage memory automatically.
• Amortized O(n)：雖然單一字串拼接可能擴容，但整體加起來仍是線性時間。Although individual appends may resize, the total work across all appends is still linear.

思路

最直觀的暴力法是真的開一個二維字元矩陣，模擬鋸齒形把字元一個個放進去，最後再從上到下、從左到右掃描矩陣、跳過空格輸出。這當然會得到正確答案，但需要 numRows * n 的空間（其中 n = s.length()），而且大部分格子都是空白，浪費很多記憶體，也得處理「哪些格子是空的」這種噁心的細節。觀察輸出規律可以發現：每個字元最終一定屬於某一列，而它屬於哪一列只取決於我們走到它時的「目前列索引」。所以我們其實只要為每一列各自維護一個字串緩衝區，依序遍歷 s，把每個字元 append 到對應列的緩衝區，再把所有緩衝區依序串起來即可。關鍵在於「目前列」是怎麼變化的：從第 0 列開始，先一路往下走到第 numRows - 1 列，再翻轉方向往上走到第 0 列，如此往復——這正是鋸齒的本質。我們用一個方向變數（+1 表示往下、-1 表示往上）來追蹤，每當碰到頂列或底列就翻轉方向。特別注意 numRows == 1 時方向永遠不會翻轉（頂底是同一列），會卡死，所以要先特判直接回傳原字串。

The brute-force idea is to literally allocate a 2D character grid, simulate the zigzag walk to fill characters cell by cell, then scan the grid row by row skipping blanks. It works but uses numRows * n space (where n = s.length()), wastes most cells on blanks, and forces you to handle "is this cell empty?" logic. The key insight is that every character ends up in exactly one row, and which row it lands in depends only on the current row index as we walk the zigzag. So we maintain one string buffer per row, iterate s once, append each character to its row's buffer, and finally concatenate all buffers in order. The current-row index moves like a bouncing ball: it starts at 0, increases by 1 until it hits numRows - 1, then decreases by 1 until it returns to 0, and repeats. We track this with a direction variable (+1 for down, -1 for up) and flip it whenever we touch the top or bottom row. Watch out for numRows == 1: the top and bottom rows coincide, the direction would never flip meaningfully, and we'd index out of range — so we short-circuit and return s unchanged.

逐步走查 / Walkthrough

Trace s = "PAYPALISHIRING", numRows = 3. We keep three row buffers R0, R1, R2, a current row cur, and a direction dir (+1 = down, -1 = up).

Concatenate R0 + R1 + R2 → "PAHN" + "APLSIIG" + "YIR" → "PAHNAPLSIIGYIR". ✅

Solution — C

// 演算法 / Algorithm:
//   為每一列開一個字串緩衝區，沿著鋸齒走訪字串 s，
//   把每個字元 append 到「目前列」的緩衝區，最後把所有列依序串接。
//   Keep one buffer per row; walk s in zigzag order; append each char to
//   the current row's buffer; concatenate all rows at the end.

#include <stdlib.h>   // malloc, free — 動態記憶體 / dynamic memory
#include <string.h>   // strlen, strcpy, memcpy — 字串操作 / string ops

char* convert(char* s, int numRows) {
    int n = (int)strlen(s);                 // n 是輸入長度 / n is input length

    // 邊界情況：只有一列時不會有鋸齒，直接回傳一份拷貝即可。
    // Edge case: with 1 row there is no zigzag — return a copy of s.
    // 也處理 numRows >= n 的情況（每個字元自己一列，順序不變）。
    // Also covers numRows >= n (each char alone in its own row, order unchanged).
    if (numRows == 1 || numRows >= n) {
        char* copy = (char*)malloc((size_t)n + 1); // +1 給結尾的 '' / +1 for null terminator
        memcpy(copy, s, (size_t)n);                // 複製 n 個位元組 / copy n bytes
        copy[n] = '';                            // C 字串以 '' 結尾 / C strings end with ''
        return copy;
    }

    // rows[i] 是第 i 列的緩衝區；最壞情況一列裝下整個 s，所以給 n+1 個 byte。
    // rows[i] is row i's buffer; worst case it holds all n chars, so allocate n+1.
    char** rows = (char**)malloc(sizeof(char*) * (size_t)numRows); // 指標陣列 / array of pointers
    int*   len  = (int*) malloc(sizeof(int)   * (size_t)numRows);  // 每列目前長度 / length per row
    for (int i = 0; i < numRows; i++) {
        rows[i] = (char*)malloc((size_t)n + 1); // 為第 i 列配置空間 / allocate row i
        len[i]  = 0;                            // 初始長度為 0 / starts empty
    }

    int cur = 0;     // 目前所在列 / current row index
    int dir = 1;     // +1 表示往下，-1 表示往上 / +1 = moving down, -1 = moving up
    for (int i = 0; i < n; i++) {
        rows[cur][len[cur]++] = s[i];       // 把字元寫到目前列末端，並把該列長度 +1
                                            // append s[i] to current row and bump its length
        if (cur == 0)            dir =  1;  // 撞到頂列就改為往下 / hit top → go down
        else if (cur == numRows - 1) dir = -1; // 撞到底列就改為往上 / hit bottom → go up
        cur += dir;                         // 依方向移動到下一列 / step to next row
    }

    // 配置輸出字串：總共 n 個字元 + ''。
    // Allocate output: n chars + terminator.
    char* out = (char*)malloc((size_t)n + 1);
    int   pos = 0;                          // pos 是下一個寫入位置 / next write index
    for (int i = 0; i < numRows; i++) {
        memcpy(out + pos, rows[i], (size_t)len[i]); // 把第 i 列整段複製過去 / copy whole row i
        pos += len[i];                              // 推進寫入位置 / advance write head
        free(rows[i]);                              // 釋放第 i 列緩衝區 / free row buffer
    }
    out[n] = '';                          // 收尾 '' / terminate output
    free(rows);                             // 釋放指標陣列 / free pointer array
    free(len);                              // 釋放長度陣列 / free length array
    return out;                             // LeetCode 接管這塊記憶體 / LeetCode owns this buffer
}

Solution — C++

// 演算法 / Algorithm:
//   用 vector<string> 為每一列維護一個緩衝區，沿鋸齒走訪 s，
//   把每個字元 push 到「目前列」，最後一次把所有列拼接成答案。
//   Use vector<string> as per-row buffers; walk s in zigzag order;
//   push each char to its row; concatenate all rows at the end.

#include <string>   // std::string
#include <vector>   // std::vector

class Solution {
public:
    std::string convert(std::string s, int numRows) {
        int n = (int)s.size();                       // n 是輸入長度 / input length

        // 邊界：1 列沒有鋸齒；列數 >= 字元數時順序不變。直接回傳 s。
        // Edge: numRows == 1 means no zigzag; numRows >= n leaves order unchanged.
        if (numRows == 1 || numRows >= n) return s;

        // rows 是 numRows 個空字串組成的向量；每個元素代表一列的緩衝區。
        // rows is a vector of numRows empty strings; each element is one row's buffer.
        std::vector<std::string> rows(numRows);

        int cur = 0;    // 目前列索引 / current row index
        int dir = 1;    // +1 往下、-1 往上 / +1 down, -1 up
        for (char c : s) {              // range-for：依序取出 s 的每個字元 / iterate each char
            rows[cur].push_back(c);     // push_back 把字元加到字串尾端 / append to row buffer
            if (cur == 0)               dir =  1; // 頂列 → 改向下 / top → go down
            else if (cur == numRows - 1) dir = -1; // 底列 → 改向上 / bottom → go up
            cur += dir;                 // 移到下一列 / step to next row
        }

        // 依序串接所有列得到最終答案。
        // Concatenate all rows in order to form the answer.
        std::string out;
        out.reserve((size_t)n);         // 預先配置容量避免重新配置 / reserve to avoid realloc
        for (const std::string& r : rows) { // const & 避免複製 / const-ref to avoid copying
            out += r;                       // operator+= 在字串尾端 append / append in place
        }
        return out;                         // RVO/move：不會多一次拷貝 / no extra copy thanks to RVO/move
    }
};

複雜度 / Complexity

• Time: O(n) — 走訪 s 一次將每個字元 append 到某列（攤銷 O(1)），最後串接所有列也是把每個字元複製一次，總計線性。We touch each character a constant number of times (one append + one final copy), where n = s.length().
• Space: O(n) — 所有列緩衝區加起來恰好存下整個 s，再加上長度為 n 的輸出字串。The row buffers together hold all n chars, plus the n-char output.

Pitfalls & Edge Cases

• numRows == 1 / 只有一列：頂列即底列，方向永遠無法翻轉，cur 會一直加而越界。先特判直接回傳原字串。Top and bottom collide; without the early return, cur would walk past the last row.
• numRows >= n / 列數比字元還多：每列最多放一個字元，鋸齒永遠走不到底，但邏輯仍正確；早回傳是為了省事。Each row holds at most one char; the zigzag never bounces — return early for simplicity and a small speedup.
• C 記憶體所有權 / Memory ownership in C：必須回傳 malloc 出來的指標，LeetCode 會幫你 free。釋放 rows[i] 之後別再使用；釋放 rows、len 但不要釋放 out。Return a malloc-ed pointer; LeetCode frees it. Don't double-free rows[i], and never free out.
• 方向翻轉的順序 / Order of direction check：必須先 append 再翻轉方向再移動 cur，否則 cur 會跑到 -1 或 numRows 造成越界。Append → flip → move; otherwise cur goes out of bounds.
• std::string 隱含複製 / Hidden copies in C++：用 const std::string& 跑 range-for，避免把每一列複製一份；reserve 也能減少 out += r 時的擴容次數。Use const& in the range-for and reserve to skip unnecessary allocations.
• 空字串？/ Empty input?：題目保證 n >= 1，所以不必處理 n == 0；但加入 numRows >= n 早返回也順帶涵蓋。Constraints guarantee n >= 1; the numRows >= n early return harmlessly covers n == 1 too.