C语言判断一个字符串是否是回文（3种方法）

回文是一个有趣的语言现象，它指的是从前往后读和从后往前读都一样的字符序列。在C语言中，判断一个字符串是否为回文是一个常见的编程练习，它不仅能帮助我们理解字符串操作，还能锻炼我们的逻辑思维能力。
 

在开始编写代码之前，我们需要明确回文的定义。对于一个字符串来说，如果它正着读和倒着读都一样，那么它就是回文。例如，"level"、"radar" 和 "A man a plan a canal Panama" 都是回文。注意，在判断回文时，我们通常会忽略空格、标点符号和大小写。
 

让我们从最简单的方法开始，逐步深入探讨如何判断回文。

方法1：使用两个指针（推荐）

这种方法使用两个指针，一个从字符串的开头向右移动，另一个从字符串的末尾向左移动。我们比较这两个指针所指向的字符，如果所有字符都匹配，那么这个字符串就是回文。

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

int isPalindrome(const char *str) {
    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() {
    const char *str1 = "A man a plan a canal Panama";
    const char *str2 = "race a car";

    printf("%s is %s a palindrome.\n", str1, isPalindrome(str1) ? "" : "not");
    printf("%s is %s a palindrome.\n", str2, isPalindrome(str2) ? "" : "not");

    return 0;
}

这段代码中，我们定义了一个 isPalindrome 函数来判断字符串是否为回文。该函数使用两个指针 left 和 right，分别从字符串的开头和结尾开始移动。在比较字符时，我们跳过了非字母数字字符，并使用 tolower 函数将字符转换为小写进行比较，以忽略大小写。
 

在 main 函数中，我们测试了两个字符串。让我们看看输出结果：

A man a plan a canal Panama is  a palindrome.
race a car is not a palindrome.

这种方法的时间复杂度是 O(n)，其中 n 是字符串的长度。它只需要遍历字符串一次，因此效率较高。空间复杂度是 O(1)，因为我们只使用了常数级的额外空间。

方法2：使用递归

递归是另一种解决回文问题的方法，虽然这种方法可能不如两指针方法高效，但它可以帮助我们更好地理解问题的本质。递归的思想是：如果一个字符串的首尾字符相同，并且去掉首尾字符后的子串也是回文，那么这个字符串就是回文。

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

int isPalindromeRecursive(const char *str, int start, int end) {
    // 跳过非字母数字字符
    while (start < end && !isalnum(str[start])) start++;
    while (start < end && !isalnum(str[end])) end--;

    // 基本情况：字符串为空或只有一个字符
    if (start >= end) return 1;

    // 比较首尾字符，然后递归检查子串
    if (tolower(str[start]) != tolower(str[end])) {
        return 0;
    } else {
        return isPalindromeRecursive(str, start + 1, end - 1);
    }
}

int isPalindrome(const char *str) {
    return isPalindromeRecursive(str, 0, strlen(str) - 1);
}

int main() {
    const char *str1 = "A man a plan a canal Panama";
    const char *str2 = "race a car";

    printf("%s is %s a palindrome.\n", str1, isPalindrome(str1) ? "" : "not");
    printf("%s is %s a palindrome.\n", str2, isPalindrome(str2) ? "" : "not");

    return 0;
}

在这个实现中，我们定义了一个辅助函数 isPalindromeRecursive，它接受字符串和两个索引作为参数。这个函数首先跳过非字母数字字符，然后比较首尾字符，如果它们相同，函数会递归地检查剩余的子串。

输出结果与之前的方法相同：

A man a plan a canal Panama is  a palindrome.
race a car is not a palindrome.

这种递归方法的时间复杂度仍然是 O(n)，但由于函数调用栈的开销，它的空间复杂度变成了 O(n)。在处理非常长的字符串时，这可能会导致栈溢出的问题。

方法3：反转字符串并比较

另一种判断回文的方法是将原字符串反转，然后与原字符串进行比较。如果它们相同，那么原字符串就是回文。这种方法虽然直观，但需要额外的空间来存储反转后的字符串。

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

char* reverseString(const char *str) {
    int len = strlen(str);
    char *reversed = (char*)malloc(len + 1);
    int j = 0;

    for (int i = len - 1; i >= 0; i--) {
        if (isalnum(str[i])) {
            reversed[j++] = tolower(str[i]);
        }
    }
    reversed[j] = '\0';
    return reversed;
}

int isPalindrome(const char *str) {
    char *original = (char*)malloc(strlen(str) + 1);
    int j = 0;

    for (int i = 0; str[i]; i++) {
        if (isalnum(str[i])) {
            original[j++] = tolower(str[i]);
        }
    }
    original[j] = '\0';

    char *reversed = reverseString(str);
    int result = strcmp(original, reversed) == 0;

    free(original);
    free(reversed);
    return result;
}

int main() {
    const char *str1 = "A man a plan a canal Panama";
    const char *str2 = "race a car";

    printf("%s is %s a palindrome.\n", str1, isPalindrome(str1) ? "" : "not");
    printf("%s is %s a palindrome.\n", str2, isPalindrome(str2) ? "" : "not");

    return 0;
}

在这个实现中，我们首先定义了一个 reverseString 函数来反转字符串。然后在 isPalindrome 函数中，我们创建了一个只包含字母和数字的小写字符串，并将其与反转后的字符串进行比较。

输出结果仍然相同：

A man a plan a canal Panama is  a palindrome.
race a car is not a palindrome.

这种方法的时间复杂度是 O(n)，但空间复杂度也是 O(n)，因为我们需要额外的空间来存储反转后的字符串。虽然这种方法在某些情况下可能更容易理解，但它不如前两种方法高效。
 

在实际应用中，我们通常会选择第一种方法（两指针法）来判断回文，因为它既高效又节省内存。然而，了解多种解决问题的方法可以帮助我们在不同的场景下选择最适合的算法。