14. 字符串反转与回文：从基础到进阶

字符串处理，说白了就是跟字符数组打交道。我做了这么多年嵌入式开发，字符串反转和回文判断这两个操作，几乎每个项目都会碰到。今天咱们就把这块彻底讲透。

14.1 字符串原地反转

什么叫「原地反转」？就是不额外开数组，直接在原字符串上动手。我刚开始学C语言时，总喜欢新开一个数组来存结果，后来被老工程师骂了一顿——内存宝贵啊，兄弟。

核心思路很简单：两个指针，一个从头，一个从尾，交换字符，往中间靠拢。

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

void reverse_string(char *str) {
    if (str == NULL) return;
    
    int left = 0;
    int right = strlen(str) - 1;
    char temp;
    
    while (left < right) {
        // 交换左右字符
        temp = str[left];
        str[left] = str[right];
        str[right] = temp;
        
        left++;
        right--;
    }
}

int main() {
    char text[] = "Hello, World!";
    printf("原字符串: %s\n", text);
    
    reverse_string(text);
    printf("反转后: %s\n", text);
    
    return 0;
}

小提示：注意我用的 char text[] 而不是 char *text。用指针指向字符串常量的话，你没法修改它——我曾经在这上面栽过跟头，程序直接崩溃。

14.2 判断回文字符串

回文，就是正着读反着读都一样。比如 "level"、"上海自来水来自海上"。判断回文其实跟反转有异曲同工之妙。

#include <stdio.h>
#include <string.h>
#include <ctype.h>  // 提供 tolower() 函数

int is_palindrome(const char *str) {
    if (str == NULL) return 0;
    
    int left = 0;
    int right = strlen(str) - 1;
    
    while (left < right) {
        // 跳过非字母数字字符（处理带标点的句子）
        while (left < right && !isalnum(str[left])) left++;
        while (left < right && !isalnum(str[right])) right--;
        
        // 忽略大小写比较
        if (tolower(str[left]) != tolower(str[right])) {
            return 0;  // 不是回文
        }
        
        left++;
        right--;
    }
    
    return 1;  // 是回文
}

int main() {
    char *tests[] = {"level", "Hello", "A man, a plan, a canal: Panama", "race a car"};
    
    for (int i = 0; i < 4; i++) {
        printf("\"%s\" -> %s\n", tests[i], 
               is_palindrome(tests[i]) ? "是回文" : "不是回文");
    }
    
    return 0;
}

关键点：实际项目中，回文判断往往要考虑大小写和标点符号。比如 "A man, a plan, a canal: Panama" 去掉标点、忽略大小写后，确实是回文。我当年面试时就因为没考虑这个被扣分了。

14.3 最长回文子串

这个就有点意思了。给你一个字符串，找出最长的那个回文子串。比如 "babad" 中，"bab" 和 "aba" 都是答案。

我常用的方法是「中心扩展法」。说白了，就是遍历每个字符，以它为中心向两边扩展，看看能扩多远。

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

// 从中心向两边扩展，返回回文子串的起始和结束位置
void expand_around_center(const char *str, int left, int right, 
                          int *start, int *max_len) {
    int len = strlen(str);
    
    while (left >= 0 && right < len && str[left] == str[right]) {
        left--;
        right++;
    }
    
    // 当前回文长度
    int cur_len = right - left - 1;
    if (cur_len > *max_len) {
        *max_len = cur_len;
        *start = left + 1;
    }
}

void longest_palindrome(const char *str) {
    if (str == NULL || strlen(str) < 1) return;
    
    int len = strlen(str);
    int start = 0;
    int max_len = 1;
    
    for (int i = 0; i < len; i++) {
        // 奇数长度回文：中心是一个字符
        expand_around_center(str, i, i, &start, &max_len);
        // 偶数长度回文：中心是两个字符之间
        expand_around_center(str, i, i + 1, &start, &max_len);
    }
    
    // 输出结果
    printf("最长回文子串: ");
    for (int i = start; i < start + max_len; i++) {
        putchar(str[i]);
    }
    printf(" (长度: %d)\n", max_len);
}

int main() {
    char *tests[] = {"babad", "cbbd", "a", "ac"};
    
    for (int i = 0; i < 4; i++) {
        printf("输入: \"%s\"\n", tests[i]);
        longest_palindrome(tests[i]);
        printf("\n");
    }
    
    return 0;
}

注意：中心扩展法的时间复杂度是 O(n²)，空间复杂度 O(1)。对于长字符串（比如几千个字符），这个算法够用。但如果字符串有几百万字符，你得考虑 Manacher 算法——那个是 O(n) 的，不过实现起来复杂不少。

14.4 知识体系总览

下面这张图，把本章的核心逻辑串起来了。我建议你多看几遍，理解每个知识点之间的联系。

字符串反转与回文 - 知识体系 字符串处理 字符串原地反转 双指针法 原地交换 回文字符串判断 忽略大小写 跳过标点符号 最长回文子串 中心扩展法 奇偶两种情况 核心思想：双指针 + 中心扩展 时间复杂度：反转 O(n) | 回文判断 O(n) | 最长回文子串 O(n²) 空间复杂度：所有算法均为 O(1) 原地操作

14.5 避坑指南

我这些年踩过的坑，给你列出来，省得你再走一遍弯路。

  • 字符串常量不能修改：用 char *p = "hello" 然后试图反转？程序直接崩。记得用字符数组 char arr[] = "hello"。
  • 空字符串和单字符：空字符串反转还是空，单字符反转还是它自己。边界条件一定要处理。
  • 中文字符串：C语言里一个中文字符占多个字节，直接用上面的方法会乱码。处理中文时得用宽字符 wchar_t。
  • 性能陷阱：最长回文子串如果用暴力法（三重循环），O(n³) 的时间复杂度，字符串稍微长点就跑不动了。中心扩展法 O(n²) 是性价比最高的选择。

我的习惯：写字符串处理函数时，我总会先加一个 if (str == NULL) return; 的判断。别嫌啰嗦，线上环境里空指针导致的崩溃，我见过太多次了。

好了，字符串反转和回文这块就讲到这里。代码不多，但每个函数背后都有值得琢磨的细节。你写代码时多想想边界情况，多测试几种输入，慢慢就能写出健壮的程序了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →