C/C++ 經典演練：遞迴判斷迴文字串

問題定義

迴文：正讀反讀相同的字串 (忽略空格與標點)。如 "radar", "able was i ere i saw elba"。

編寫遞迴函式 testPalindrome，若為迴文回傳 true，否則 false。

參考實作

#include <stdio.h>
#include <ctype.h>  // for isalnum, tolower

// 輔助：跳過非字母數字
int next_valid(const char *s, int idx, int len, int dir) {
    while (idx >= 0 && idx < len && !isalnum((unsigned char)s[idx]))
        idx += dir;
    return idx;
}

// 遞迴核心
int is_pal_rec(const char *s, int left, int right) {
    left = next_valid(s, left, right + 1, 1);
    right = next_valid(s, right, right + 1, -1);
    if (left >= right) return 1;
    if (tolower((unsigned char)s[left]) != tolower((unsigned char)s[right]))
        return 0;
    return is_pal_rec(s, left + 1, right - 1);
}

int testPalindrome(const char *s) {
    int len = 0;
    while (s[len]) len++;
    return is_pal_rec(s, 0, len - 1);
}

int main() {
    char buf[256];
    fgets(buf, sizeof(buf), stdin);
    // 移除尾部換行
    char *p = strchr(buf, '\n');
    if (p) *p = '\0';
    printf(testPalindrome(buf) ? "是迴文\n" : "不是迴文\n");
    return 0;
}

演算法說明

1. 雙指標從兩端向中間收斂。
2. 跳過非字母數字字元 (isalnum)。
3. 大小寫不敏感比較 (tolower)。
4. 遞迴終止條件：left >= right。

複雜度

• 時間：O(n)，每個字元最多處理一次。
• 空間：O(n) 遞迴呼叫棧 (可改寫成迴圈 O(1) 空間)。

進階提示

• C++ 可用 std::string + std::isalnum + lambda 更簡潔。
• 若需支援 Unicode，請使用 ICU 庫或 C++20 std::u8string 配合 std::tolower (需 locale)。