当前位置：首页 > article >正文

LeetCode 面试题01.04回文排列

article 2025/1/8 7:34:28

判断字符串是否为回文串排列的解法

在日常的编程学习与实践中，我们经常会遇到一些有趣的字符串处理问题。今天就来和大家分享一道关于判断给定字符串是否为某个回文串的排列之一的题目。

一、题目理解

题目给定一个字符串，要求编写一个函数判定其是否为某个回文串的排列之一。这里要明确几个关键概念：回文串，它是指正反两个方向都一样的单词或短语，比如 “level”“noon” 等；排列，指的是字母的重新排列，也就是说不要求原字符串本身就是回文串，只要通过重新排列它的字符能够形成回文串就行，并且回文串不一定是字典当中的单词。

二、解题思路

不管是使用哪种编程语言来解决，核心思路都是一致的。那就是统计字符串中每个字符出现的次数，对于一个能重排成回文串的字符串而言，它最多只能有一个字符出现的次数是奇数，其余字符出现次数都应为偶数。为什么会这样呢？因为回文串从中间对折后，两边的字符是对称的，除了可能存在的中间字符（当字符串长度为奇数时），其他字符必然成对出现，也就是出现偶数次。

三、代码实现

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

bool canPermutePalindrome(char* s) {
    // 动态分配一个数组，用来模拟哈希表，统计字符出现的次数
    // 这里假设处理常见的 ASCII 码字符范围（0 - 127），所以数组大小为 128
    int* count = (int*)malloc(128 * sizeof(int));
    // 将数组元素初始化为 0，方便后续统计
    memset(count, 0, 128 * sizeof(int));

    // 开始遍历给定的字符串，统计每个字符出现的次数
    for (int i = 0; i < strlen(s); i++) {
        count[s[i]]++;
    }

    int oddCount = 0;
    // 再次遍历统计数组，统计出现奇数次的字符个数
    for (int i = 0; i < 128; i++) {
        if (count[i] % 2 == 1) {
            oddCount++;
        }
    }

    // 释放之前动态分配的内存，避免内存泄漏，这可是很重要的哦
    free(count);

    // 根据出现奇数次字符的个数来判断，若不超过 1 个，就说明可以重排为回文串
    return oddCount <= 1;
}

一开始，咱们使用 malloc 函数动态分配了一个大小为 128 * sizeof(int) 的内存空间，这个空间就是咱们用来统计字符出现次数的数组 count 啦，它的下标对应着字符的 ASCII 码值，而数组元素的值呢，就代表了相应字符出现的次数哦。然后通过 memset 函数把整个数组的元素都初始化为 0，为后面准确的计数做好准备呀。
接着呢，就用一个 for 循环来遍历输入的字符串 s 啦，在循环里，每次遇到一个字符，就以它的 ASCII 码值作为下标，把 count 数组对应下标的元素值加 1，这样就完成了对字符串中每个字符出现次数的统计工作咯。
之后呀，再用一个 for 循环去遍历 count 数组，在这个过程中，通过判断每个元素除以 2 的余数是不是等于 1，来确定这个字符出现的次数是不是奇数，如果是奇数，就把记录奇数次字符个数的变量 oddCount 加 1 呀。
最后呢，可别忘了使用 free 函数把之前动态分配的内存释放掉呀，不然就会出现内存泄漏的问题啦。然后根据 oddCount 的值来做最后的判断，如果 oddCount 不超过 1，那就说明这个字符串是可以通过重新排列变成回文串的，函数就返回 true；要是 oddCount 大于 1 了，那就返回 false 啦。

四、代码优化：限定字符范围

要是咱们事先知道要处理的字符范围是有限的，比如说只处理小写字母的情况，那代码还能进一步优化一下呢，来看看下面的代码吧：

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

bool canPermutePalindrome(char* s) {
    // 定义一个数组，专门用来统计 26 个小写字母出现的次数，初始化为 0
    int count[26] = {0};

    // 遍历字符串，统计每个小写字母出现的次数
    for (int i = 0; i < strlen(s); i++) {
        // 通过把字符减去 'a' 的 ASCII 码值，将字符映射到 0 - 25 的下标范围
        // 这样就能很方便地在 count 数组里进行计数啦
        count[s[i] - 'a']++;
    }

    int oddCount = 0;
    // 统计出现奇数次的字符个数
    for (int i = 0; i < 26; i++) {
        if (count[i] % 2 == 1) {
            oddCount++;
        }
    }

    // 根据奇数次字符个数判断是否能重排为回文串
    return oddCount <= 1;
}

在这个优化后的代码里呀：

首先定义了一个长度为 26 的数组 count，它就是专门用来统计 26 个小写字母出现次数的哦，并且一开始就把数组元素都初始化为 0 啦。
然后在遍历字符串 s 的时候呢，通过巧妙地把每个字符减去 'a' 的 ASCII 码值，就能把小写字母 a 到 z 分别对应到数组 count 的下标 0 到 25 啦，这样每次遇到一个小写字母，就可以直接在对应的下标位置把计数加 1，轻松完成对小写字母出现次数的统计工作呢。
后续的步骤就和前面类似啦，再用一个 for 循环去统计出现奇数次的字符个数 oddCount，最后根据 oddCount 的值来判断这个字符串能不能通过重新排列变成回文串，返回相应的结果哦。

通过这两种不同的 C 语言代码实现方式，咱们就能很好地解决判断字符串是否为回文串排列之一的这个问题啦。希望大家在学习的过程中，能够多动手实践，这样就能更深入地理解这些代码背后的逻辑和技巧咯，以后遇到类似的字符串处理问题，也就能轻松应对啦。

查看全文

http://www.kler.cn/a/469355.html