第12章字符串回文判断

课程目录第12章字符串回文判断

第12章 · 字符串回文判断：双指针法与递归法

回文判断，说白了就是看一个字符串正着读和反着读是不是一模一样。比如 "level"、"上海自来水来自海上"。很多初学者觉得这题简单，但真到了工程里，边界条件、空格、大小写、甚至 Unicode 组合字符都能让你栽跟头。我最早在嵌入式设备上写回文检测时，就因为没考虑字符串中间的空格，导致一个串口指令解析出了大 bug。嗯，从那以后我对回文就多了一份敬畏。

这一章我们聚焦两种最经典的实现思路：双指针法 和 递归法。我会结合代码、复杂度分析，还有我个人的踩坑经历，把这两个方法彻底讲透。

12.1 双指针法 · 从两端向中间逼近

双指针法是我个人最常用的方法。思路特别直白：一个指针 left 指向字符串开头，另一个 right 指向末尾。然后逐对比较字符。如果发现不一样，直接返回 false；如果一直相同直到 left >= right，那就是回文。

你可能会问：那空格、标点、大小写怎么办？好问题。在实际项目中，比如处理用户输入的验证码或者自然语言，经常需要忽略非字母数字字符。我曾在日志分析中遇到一个坑：一个看似回文的句子 "A man, a plan, a canal: Panama" 如果直接比较，肯定失败。所以我们需要预处理——要么在比较时跳过无效字符，要么先过滤再判断。

        双指针法核心：每次移动指针前跳过非字母数字，然后忽略大小写比较。
    

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

bool isPalindrome_twoPointers(const char *s) {
    if (s == NULL) return false;
    int left = 0;
    int right = strlen(s) - 1;

    while (left < right) {
        // 跳过左侧非字母数字
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        // 跳过右侧非字母数字
        while (left < right && !isalnum(s[right])) {
            right--;
        }
        // 忽略大小写比较
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

你看，代码很紧凑。但这里有个细节：while (left < right && !isalnum(...)) 里面的 left < right 条件不能少。我曾经漏掉这个，当字符串全是标点时，指针会越界。嗯，血的教训。

如果字符串中只包含字母（无空格标点），可以去掉跳过逻辑，直接用 tolower(s[left]) != tolower(s[right]) 比较。性能会更好。

12.2 递归法 · 分而治之的优雅

递归法更符合“数学归纳”的思维：如果字符串首尾字符相同，并且去掉首尾的子串也是回文，那么整个字符串就是回文。基线条件：字符串长度 ≤ 1 时，一定是回文。

我刚开始用递归写回文时，觉得这代码真漂亮——就几行。但后来在嵌入式项目里，递归的栈空间让我吃了苦头。一个 1000 字符的字符串，递归深度 500，栈直接爆了。所以递归法更适合教学或长度可控的场景。

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>

// 辅助函数：递归判断子串 [l, r] 是否回文
bool isPalindromeRecur(const char *s, int l, int r) {
    // 基线条件
    if (l >= r) return true;

    // 跳过非字母数字
    if (!isalnum(s[l])) return isPalindromeRecur(s, l + 1, r);
    if (!isalnum(s[r])) return isPalindromeRecur(s, l, r - 1);

    // 比较当前字符（忽略大小写）
    if (tolower(s[l]) != tolower(s[r])) return false;

    // 递归检查内部子串
    return isPalindromeRecur(s, l + 1, r - 1);
}

bool isPalindrome_recursive(const char *s) {
    if (s == NULL) return false;
    return isPalindromeRecur(s, 0, strlen(s) - 1);
}

注意看：递归函数里跳过了非字母数字，这和双指针法的思路一致。但每次递归调用都会压栈，参数包括指针和两个整数。我建议在递归深度可能超过几百时，改用迭代或者显式栈。

递归法在极端情况下（如超长字符串）可能导致栈溢出。C 语言标准未规定栈大小，嵌入式环境往往只有 1~4KB。如果你在 RTOS 或单片机里写回文检测，请用双指针法。

12.3 两种方法对比 · 选型指南

我把两种方法的特性整理成了一张表，方便你根据场景选择。

维度	双指针法	递归法
时间复杂度	O(n)	O(n)
空间复杂度	O(1) (仅指针变量)	O(n) (递归栈深度)
代码可读性	中等，逻辑直观	简洁，数学归纳风格
工程健壮性	高，无栈溢出风险	低，深度依赖输入长度
适用场景	生产环境、嵌入式、大字符串	教学、竞赛、短字符串

我个人习惯：只要是产品代码，一律用双指针。递归法我通常只在写算法演示或者 LeetCode 每日一题时用。你想想看，如果线上服务因为一个超长回文请求导致栈溢出 crash，那得多冤。

12.4 避坑指南 · 我踩过的三个坑

讲真，回文判断的坑比大多数人想象的多。下面三个是我亲身经历过的，分享给你。

坑一：空字符串和 NULL 指针 —— 空字符串 "" 应该返回 true（空串是回文），但 NULL 指针应该返回 false 或者做防御处理。我早期代码没判 NULL，结果在某个配置项为空时直接段错误。
坑二：中文字符和多字节编码 —— C 语言的 char 默认是单字节，而 UTF-8 中文占 3 字节。直接用 s[left] 比较会拆散汉字。我建议在需要处理中文时，使用宽字符 wchar_t 或者专门的 Unicode 库。不过本章我们只讨论 ASCII 字母数字场景。
坑三：跳过字符时忘记更新指针 —— 在双指针的 while 循环里，如果左右指针都跳过了非字母数字，但忘记最后执行 left++ 和 right--，就会死循环。我曾经调试了半小时才发现少写了一行。

        总结一个安全模板：先判 NULL → 初始化左右指针 → 循环内先跳过无效字符 → 比较 → 移动指针。每一步都检查边界。
    

12.5 一个综合示例 · 忽略非字母数字的回文检测

下面我把双指针法封装成一个完整的函数，包含错误处理和大小写归一化。你可以直接复制到项目里用。

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome_robust(const char *str) {
    if (str == NULL) return false;
    int len = strlen(str);
    if (len == 0) return true;   // 空串视为回文

    int l = 0, r = len - 1;
    while (l < r) {
        // 跳过非字母数字
        while (l < r && !isalnum((unsigned char)str[l])) l++;
        while (l < r && !isalnum((unsigned char)str[r])) r--;

        if (tolower((unsigned char)str[l]) != tolower((unsigned char)str[r])) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

// 测试用例
int main() {
    const char *tests[] = {
        "A man, a plan, a canal: Panama",
        "race a car",
        " ",
        "abba",
        NULL
    };
    for (int i = 0; i < 4; i++) {
        printf("\"%s\" -> %s\n", tests[i] ? tests[i] : "NULL",
               isPalindrome_robust(tests[i]) ? "true" : "false");
    }
    return 0;
}

注意我用了 (unsigned char) 强制转换，这是因为 isalnum 和 tolower 要求参数在 unsigned char 范围内，否则在有些平台上会有未定义行为。这个细节，很多老手都会忽略。

12.6 扩展思考 · 如果字符串很长怎么办？

假设你要检测一个 10MB 的日志文件是否为回文（当然实际很少这么干）。双指针法仍然只需要两个指针，但 strlen 本身就要 O(n) 遍历一次。你可以用 fseek 定位文件尾，或者用内存映射文件。递归法在这种规模下基本不可行——栈会爆炸。

另外，如果你需要检测“回文子串”而不是整个字符串，那就要用中心扩展法或马拉车算法（Manacher）。那是后面章节的内容，这里先埋个伏笔。

在嵌入式或实时系统中，如果字符串可能来自不可信源（比如网络输入），一定要做长度检查。我见过一个攻击者发送超长回文串导致递归栈溢出的案例。用双指针 + 最大长度限制，安全又高效。

好了，关于回文判断的双指针法和递归法，我就讲到这里。两种方法各有千秋，但工程上我坚定选择双指针。你可以在自己的代码里都试试，感受一下递归的简洁和双指针的踏实。下一章我们会聊更复杂的字符串匹配算法，但今天先把回文这个基本功练扎实。

📚 课程目录