C语言中重排字符串生成回文的方法及O(n)时间O(1)空间实现
回文重排的前置可行性判定
首先要明确:不是所有字符串都能重排成回文,判定规则完全基于字符出现频次:
- 若原字符串长度为偶数:所有字符的出现次数必须全部为偶数,否则无法构成回文
- 若原字符串长度为奇数:有且最多只能有1个字符的出现次数为奇数,其余字符出现次数均为偶数,否则无法构成回文
在C语言的常规开发场景中,处理的字符串通常基于单字节字符集(ASCII/Latin1等),字符总种类数是固定上限(最多256种,对应unsigned char的取值范围),这个特性刚好可以用来做常数空间的计数统计,满足O(1)空间的要求。
满足O(n)时间、O(1)空间的原地重排实现方案
这个方案完全基于原字符串的内存区域修改,不需要开辟和原字符串等长的临时缓冲区,整体时间和空间复杂度符合要求,具体步骤如下:
- 第一遍遍历原字符串,用固定大小(256长度)的整型数组做字符计数,同时统计字符串总长度。这一遍的时间是O(n),计数数组的大小是固定值,完全不随字符串长度变化,属于O(1)空间开销。
- 遍历计数数组,检查是否满足回文的频次要求;如果不满足直接返回无法重排的标识。如果字符串长度为奇数,记录下那个出现奇数次的字符,把它放到原字符串的正中间索引位置,同时把该字符的计数减1,此时所有字符的计数都变为偶数。
- 初始化两个指针:左指针
l从索引0开始向右移动,右指针r从索引n-1开始向左移动。接着遍历计数数组里的每个字符:- 对每个字符c,取它的可用计数
count[c],每次在l和r位置各放一个c,放完后l右移1位、r左移1位,直到该字符的计数降到0 - 当所有字符放置完成,原字符串就已经被改成合法回文串了,整个过程只对原字符串的每个位置做一次写入,整体时间为O(n)
- 对每个字符c,取它的可用计数
常见误区:很多实现会选择开辟和原字符串等大的临时缓冲区拼接回文前后半段,这种写法的空间复杂度是O(n),不满足题目的常数空间要求;上述的原地重排逻辑完全避免了这类额外内存开销。
方案的边界注意事项
- 这里的O(1)空间是严格成立的:所有用到的临时变量(固定长度的计数数组、两个指针、字符串长度值、奇数字符的临时存储)的大小都和输入字符串的长度n完全无关,没有根据n的大小动态申请内存,不会出现输入越长、临时内存占用越高的问题。
- C语言处理字符串时要注意边界:遍历计数、修改字符位置时不要超出原字符串的内存范围,不要覆盖末尾的
'\0'结束符。 - 如果处理的是多字节编码的字符串(比如UTF-8),只要编码的总字符种类存在全局固定上限(比如Unicode的编码空间),这个方案的常数空间特性依然成立;但如果是没有固定上限的自定义字符集,就无法满足严格的O(1)空间要求。
内容的提问来源于stack exchange,提问作者Tariq Ganem
相关产品推荐
相关产品推荐

