/*
 * Algorithm: Vertical scanning / 縱向掃描
 * 用第一個字串當參考，逐欄比對所有字串。第一個出現不一致 (或某字串到結尾) 的位置，
 * 就是 LCP 的長度。把該長度的字首複製到一塊新配置的記憶體並回傳。
 * Use strs[0] as the reference; scan column-by-column. The first column where any
 * string disagrees (or ends) determines the LCP length. Copy that prefix into a
 * freshly malloc'd buffer and return it.
 */

#include <stdlib.h>   // malloc — 動態配置記憶體 / for malloc
#include <string.h>   // strlen, memcpy — 字串長度與複製 / for strlen and memcpy

char* longestCommonPrefix(char** strs, int strsSize) {
    // 邊界情況：陣列為空時回傳空字串 (constraint 保證 >=1，但保險起見還是處理)
    // Edge case: empty array — by constraints strsSize >= 1, but we guard anyway.
    if (strsSize == 0) {
        char* empty = (char*)malloc(1);   // 配置 1 個 byte 給結尾符 / 1 byte for '\0'
        empty[0] = '\0';                  // 設成空字串 / make it the empty string
        return empty;
    }

    // i 代表目前正在檢查第幾欄 (從 0 開始) / i is the current column index (0-based)
    int i = 0;

    // 外層迴圈會一直跑，直到我們在某個位置 break 出去 / loop until we break on mismatch or end
    while (1) {
        // 拿第一個字串第 i 個字元當作「期望值」 / take strs[0][i] as the expected character
        char c = strs[0][i];

        // 如果第一個字串已經到結尾，就無法再往前推了 / if strs[0] ended, LCP can't grow further
        if (c == '\0') break;

        // 從第二個字串開始，逐一檢查它們的第 i 個字元 / check every other string at column i
        for (int j = 1; j < strsSize; j++) {
            // 條件 1: strs[j] 在位置 i 已經是結尾 (字串太短) / strs[j] is too short
            // 條件 2: strs[j][i] 跟期望值 c 不同 / character differs from c
            // 任一條件成立 => 整個函式都該結束，回傳到目前為止的前綴
            // Either condition means the LCP stops here — bail out completely.
            if (strs[j][i] == '\0' || strs[j][i] != c) {
                goto done;   // 用 goto 一次跳出兩層迴圈 / break out of both loops
            }
        }

        // 這一欄全部相等，前綴可以延伸一個字元 / this column matched, extend the prefix
        i++;
    }

done:
    // i 現在等於 LCP 的長度 / i is now the length of the LCP

    // 配置 i+1 個 byte：i 個字元 + 1 個結尾符 '\0' / allocate i chars + null terminator
    // LeetCode 規定回傳值必須在 heap 上 (不能是 stack 上的區域陣列)
    // LeetCode requires heap-allocated return values; stack arrays vanish on return.
    char* result = (char*)malloc((size_t)i + 1);

    // 從 strs[0] 複製前 i 個字元到 result / copy the first i chars from strs[0]
    memcpy(result, strs[0], (size_t)i);

    // 在末尾加上 '\0'，這樣 C 才知道字串到這裡結束 / null-terminate so it's a valid C string
    result[i] = '\0';

    return result;   // 回傳給 LeetCode 評分系統 / hand the string back to LeetCode
}