C语言，如何判断一个字符串是否为回文？

C语言判断回文字符串

在C语言中，判断一个字符串是否是回文（palindrome）可以通过以下几种方法实现，回文是指正读和反读都相同的字符串，如"level"、"madam"等。

双指针法

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPalindrome(const char *str) {
    int left = 0;
    int right = strlen(str) - 1;
    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
int main() {
    char str1[] = "level";
    char str2[] = "hello";
    printf("%s 是回文吗? %s\n", str1, isPalindrome(str1) ? "是" : "否");
    printf("%s 是回文吗? %s\n", str2, isPalindrome(str2) ? "是" : "否");
    return 0;
}

递归法

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPalindromeRecursive(const char *str, int left, int right) {
    if (left >= right) {
        return true;
    }
    if (str[left] != str[right]) {
        return false;
    }
    return isPalindromeRecursive(str, left + 1, right - 1);
}
bool isPalindrome(const char *str) {
    return isPalindromeRecursive(str, 0, strlen(str) - 1);
}
int main() {
    char str1[] = "madam";
    char str2[] = "programming";
    printf("%s 是回文吗? %s\n", str1, isPalindrome(str1) ? "是" : "否");
    printf("%s 是回文吗? %s\n", str2, isPalindrome(str2) ? "是" : "否");
    return 0;
}

反转字符串比较法

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
void reverseString(char *str) {
    int left = 0;
    int right = strlen(str) - 1;
    while (left < right) {
        char temp = str[left];
        str[left] = str[right];
        str[right] = temp;
        left++;
        right--;
    }
}
bool isPalindrome(const char *str) {
    char *copy = strdup(str); // 创建字符串副本
    if (copy == NULL) {
        return false;
    }
    reverseString(copy);
    bool result = (strcmp(str, copy) == 0);
    free(copy);
    return result;
}
int main() {
    char str1[] = "racecar";
    char str2[] = "world";
    printf("%s 是回文吗? %s\n", str1, isPalindrome(str1) ? "是" : "否");
    printf("%s 是回文吗? %s\n", str2, isPalindrome(str2) ? "是" : "否");
    return 0;
}

注意事项

1. 上述方法都区分大小写，如果需要不区分大小写的比较,可以在比较前将字符统一转换为小写或大写。
2. 方法一（双指针法）是最优解，时间复杂度为O(n)，空间复杂度为O(1)。
3. 方法三需要额外的空间来存储字符串副本，空间复杂度为O(n)。
4. 对于包含空格或标点符号的字符串，需要先预处理（去除非字母字符并统一大小写）。

不区分大小写的版本示例

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
bool isPalindromeCaseInsensitive(const char *str) {
    int left = 0;
    int right = strlen(str) - 1;
    while (left < right) {
        // 跳过非字母字符
        while (left < right && !isalpha(str[left])) left++;
        while (left < right && !isalpha(str[right])) right--;
        if (tolower(str[left]) != tolower(str[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
int main() {
    char str1[] = "A man, a plan, a canal: Panama";
    char str2[] = "race a car";
    printf("%s 是回文吗? %s\n", str1, isPalindromeCaseInsensitive(str1) ? "是" : "否");
    printf("%s 是回文吗? %s\n", str2, isPalindromeCaseInsensitive(str2) ? "是" : "否");
    return 0;
}

这些方法可以根据具体需求选择使用,其中双指针法通常是最高效和最常用的解决方案。