面試必考：迴文判斷的三種實作與多核優化

什麼是迴文？

迴文指正反讀皆相同的字串，如 "a"、"aba"、"strarts"。面試常考此題，考察基本編碼、邊界處理、遞歸思維、平行化能力。

版本一：迭代雙指針（標準解）

bool isSymbolRight(const char* str, int len) {
    for (int i = 0; i < len; i++) {
        char c = str[i];
        if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))) return false;
    }
    return true;
}

bool isPalindromeIter(const char* str, int len) {
    if (!str || len == 0) return false;
    if (!isSymbolRight(str, len)) return false;  // 僅允許字母

    for (int i = 0; i < (len >> 1); i++) {
        if (str[i] != str[len - 1 - i]) return false;
    }
    return true;
}

複雜度：時間 O(n)、空間 O(1)。優點：簡單、無堆疊溢位風險。

版本二：遞歸實作（展示思維深度）

bool isPalindromeRecHelper(const char* str, int len) {
    if (len == 0 || len == 1) return true;
    return (str[0] == str[len - 1]) ? isPalindromeRecHelper(str + 1, len - 2) : false;
}

bool isPalindromeRec(const char* str, int len) {
    if (!str || len == 0) return false;
    if (!isSymbolRight(str, len)) return false;
    return isPalindromeRecHelper(str, len);
}

複雜度：時間 O(n)、空間 O(n) 堆疊幀。缺點：長字串可能堆疊溢位；尾遞歸優化視編譯器而定。

版本三：OpenMP 多核平行化（大數據量優化）

當需檢查 1000 萬個字串時，可將單字串檢查平行化：將字串前半段分塊，各執行緒檢查對應區段。

bool checkSegment(const char* str, int start, int end, int segLen) {
    for (int i = 0; i < segLen; i++) {
        if (str[start + i] != str[end - 1 - i]) return false;
        char c = str[start + i];
        if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))) return false;
    }
    return true;
}

bool isPalindromeParallel(const char* str, int len) {
    if (!str || len == 0) return false;

    int half = len >> 1;
    int quarter = half >> 1;  // 分兩段
    int start[2] = {0, quarter};
    int end[2] = {len, len - quarter};
    int segLen = quarter;
    bool results[2] = {false, false};

    #pragma omp parallel for
    for (int i = 0; i < 2; i++) {
        results[i] = checkSegment(str, start[i], end[i], segLen);
    }
    return results[0] && results[1];
}

適用場景：超長字串（如基因序列、百萬位數字）、批量檢查大量字串。注意：短字串平行化開銷大於收益；需開啟 OpenMP 編譯旗標（-fopenmp / /openmp）。

面試加分點總結

工程落地建議

1. 預設用迭代版：簡單、健壯、無平台依賴。
2. 遞歸版作為備選答案：展示對遞歸、堆疊幀的理解。
3. 平行化僅在證實為瓶頸時引入：先測量、再優化；注意 Amdahl 定律。
4. 完整驗證矩陣：空字串、單字元、奇/偶長度、含非字母、超長字串、UTF-8 多位元組字元（需改用 wchar_t/char32_t）。