// 演算法 / 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 給結尾的 '\0' / +1 for null terminator
        memcpy(copy, s, (size_t)n);                // 複製 n 個位元組 / copy n bytes
        copy[n] = '\0';                            // C 字串以 '\0' 結尾 / C strings end with '\0'
        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 個字元 + '\0'。
    // 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] = '\0';                          // 收尾 '\0' / terminate output
    free(rows);                             // 釋放指標陣列 / free pointer array
    free(len);                              // 釋放長度陣列 / free length array
    return out;                             // LeetCode 接管這塊記憶體 / LeetCode owns this buffer
}