演算法面試必考：回文判斷的多種實現與並行優化

題目定義

回文：字串正反讀相同。如 "a"、"aba"、"strarts"。限制：僅含大小寫英文字母。這看似簡單的題目，實際考察：邊界處理、多種演算法思維、擴展性設計、並行化能力。

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

int is_symbol_valid(const char *s, int len) {
    for (int i = 0; i < len; ++i) {
        char c = s[i];
        if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')))
            return 0;
    }
    return 1;
}

int is_palindrome_iter(const char *s, int len) {
    if (!s || len == 0) return 0;
    if (!is_symbol_valid(s, len)) return 0;

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

版本二：遞迴實現（面試常見追問）

int _is_palindrome_rec(const char *s, int len) {
    if (len <= 1) return 1;
    return (s[0] == s[len-1]) ? _is_palindrome_rec(s + 1, len - 2) : 0;
}

int is_palindrome_rec(const char *s, int len) {
    if (!s || len == 0) return 0;
    if (!is_symbol_valid(s, len)) return 0;
    return _is_palindrome_rec(s, len);
}

遞迴缺點：呼叫棧深度 O(n)，長字串恐溢位；尾遞迴優化需編譯器支援。

版本三：OpenMP 並行化（大數據量場景）

假設需檢查 1000 萬字串，利用多核心並行切分比較區間。

#include 

int _check_range(const char *s, int start, int end, int len) {
    for (int i = 0; i < len; ++i) {
        if (s[start + i] != s[end - 1 - i]) return 0;
        char c = s[start + i];
        if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))) return 0;
    }
    return 1;
}

int is_palindrome_parallel(const char *s, int len) {
    if (!s || len == 0) return 0;

    int half = len >> 1;
    int mid = half >> 1;  // 分成前後兩段
    int results[2] = {0};

    #pragma omp parallel for
    for (int t = 0; t < 2; ++t) {
        int start = t * mid;
        int end = len - start;
        int seg_len = (t == 0) ? mid : (half - mid);
        results[t] = _check_range(s, start, end, seg_len);
    }
    return results[0] && results[1];
}

方案對比

進階擴展思考

1. 忽略大小寫/非字母：雙指針移動時跳過非法字元，比較 tolower
2. 最長回文子串：Manacher 演算法 O(n)、動態規劃 O(n²)、中心擴展 O(n²)
3. 流式判斷：Rolling Hash（Rabin-Karp）單向掃描 O(1) 空間
4. 分散式檢查：MapReduce 切分字串，Map 階段局部比較，Reduce 聚合

面試回答策略

1. 先寫最簡潔正確的迴圈版，解釋邊界條件（空指標、長度 0/1、字元驗證）
2. 主動提出遞迴版，並分析棧溢位風險
3. 若面試官問大數據/高效能，給出並行/分散式思路，說明切分策略與同步機制
4. 最後總結：正確性 > 可讀性 > 效能，除非有具體效能指標需求

測試用例建議

// 正例
"a", "aa", "aba", "abba", "racecar", "Able was I ere I saw Elba" (預處理後)
// 反例
"", "ab", "abc", "abca", "0a0", "a b a"
// 邊界
NULL 指標、極長字串 (10^7)、全相同字元、單一非法字元

結語

回文判斷雖小，卻能折射出工程師的基礎功力、思維廣度、工程落地能力。從雙指針到遞迴再到並行化，每一步都在考驗對複雜度、資源限制、擴展性的權衡。平時多積累演算法變體與優化套路，面試時才能游刃有餘。