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

C 语言实战：字符串左旋与旋转判断的高效解法

news 2026/7/14 7:49:15

踩坑实录：从 “越写越乱” 到 “一行核心逻辑”，我搞定了字符串旋转问题

今天刷题时，我接连遇到两道字符串旋转相关的题：一个是实现字符串左旋，另一个是判断一个字符串是否是另一个的旋转结果。本来以为是小问题，结果代码越改越长，踩了一堆坑。折腾了大半天，终于从暴力模拟转向了优雅解法，记录一下这个 “拨乱反正” 的过程。

最初的暴力思路：代码越写越臃肿

第一步：实现字符串左旋（从打印到生成）

最开始我想的是 “暴力模拟旋转”：把字符串分成前 n 个字符和剩下的部分，先打印后半段，再打印前半段，就完成左旋了。于是有了第一版仅打印的代码：

void Reverse(char* p,int n) { if (p == NULL || *p == '\0') { return; } char* p1 = p; char* p2 = p; while (n) { p1++; n--; } printf("%s", p1); while (p2<p1) { printf("%c", *p2); p2++; } }

这段代码只能打印结果，没法保存旋转后的字符串，完全没法支撑第二道 “判断旋转字符串” 的题。于是我开始迭代：

新增输出缓冲区，把旋转结果存下来
加了空指针、空字符串、旋转位数越界的判断
用返回值区分成功失败

结果代码直接膨胀成这样：

int Reverse(char* p, char* p3, int n) { if (p == NULL || *p == '\0' || p3 == NULL) { return 0; } char* p1 = p; char* p2 = p; char* p4 = p3; int str_len = strlen(p); if (n >= str_len) { return 0; } while (n) { p1++; n--; } strcpy(p4, p1); while (*p4 != '\0') { p4++; } while (p2 < p1) { *p4 = *p2; p4++; p2++; } *p4 = '\0'; return 1; }

不仅逻辑绕，还出现了 “n=0 时返回失败” 的 bug—— 其实 n=0 时旋转结果就是原字符串，应该返回成功。

第二步：判断旋转字符串（暴力枚举所有可能）

有了生成旋转字符串的函数，我想的是 “遍历所有旋转位数，生成结果后逐一对比”，于是封装了IsRotateString函数：

int IsRotateString(char* src, char* target) { if (src == NULL || target == NULL || *src == '\0' || *target == '\0') { return 0; } int src_len = strlen(src); int target_len = strlen(target); if (src_len != target_len) { return 0; } char temp[1000]; for (int i = 0; i < src_len; i++) { int gen_ok = Reverse(src, temp, i); if (gen_ok == 1 && strcmp(temp, target) == 0) { return 1; } } return 0; }

这段代码能跑，但时间复杂度是 O (n²)，而且耦合度极高 —— 完全依赖Reverse函数，一旦Reverse出问题，整个判断逻辑就崩了。当时运行时还遇到 “返回值对不上” 的问题，查了半天才发现是Reverse里的边界判断没处理好。

突然开窍：原来还有更优雅的解法

折腾到这里我意识到，暴力模拟根本不是最优解。查了资料 + 自己琢磨，发现这两个问题都有 “巧解” 思路：

1. 字符串左旋：三次反转法（原地修改，O (n) 时间 + O (1) 空间）

核心原理是 “局部反转 + 整体反转”，不需要额外缓冲区：

反转前 n 个字符
反转剩余字符
反转整个字符串

比如ABCD左旋 2 位：

前 2 个反转：B A C D
剩余反转：B A D C
整体反转：C D A B→ 完美得到结果

我用这个思路重写了左旋函数，代码瞬间简洁：

void reverse(char* str, int start, int end) { while (start < end) { char temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; } } void leftRotate(char* str, int n) { if (str == NULL || *str == '\0' || n <= 0) { return; } int str_len = strlen(str); n %= str_len; // 处理n超过字符串长度的情况 reverse(str, 0, n - 1); reverse(str, n, str_len - 1); reverse(str, 0, str_len - 1); }

2. 判断旋转字符串：拼接包含法（O (n) 时间，一行核心逻辑）

这个思路更绝：如果s2是s1的旋转结果，那么s2一定是s1+s1的子串。比如s1=AABCD→s1+s1=AABCDAABCD，s2=BCDAA正好是其中的子串。

用这个思路重写判断函数，代码直接极简：

int isRotateString(char* src, char* target) { if (src == NULL || target == NULL || *src == '\0' || *target == '\0') { return 0; } int src_len = strlen(src); int target_len = strlen(target); if (src_len != target_len) { return 0; } char temp[2000] = {0}; strcpy(temp, src); strcat(temp, src); return strstr(temp, target) != NULL ? 1 : 0; }

最终整合版：

把两个最优解整合起来，补充了完整的输入输出逻辑，就得到了最终的版本：

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> // 辅助函数：反转字符串的 [start, end] 区间 void reverse(char* str, int start, int end) { while (start < end) { char temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; } } // 字符串左旋（原地修改，高效） void leftRotate(char* str, int n) { if (str == NULL || *str == '\0' || n <= 0) { return; } int str_len = strlen(str); n %= str_len; reverse(str, 0, n - 1); reverse(str, n, str_len - 1); reverse(str, 0, str_len - 1); } // 判断是否为旋转字符串（拼接包含法） int isRotateString(char* src, char* target) { if (src == NULL || target == NULL || *src == '\0' || *target == '\0') { return 0; } int src_len = strlen(src); int target_len = strlen(target); if (src_len != target_len) { return 0; } char temp[2000] = {0}; strcpy(temp, src); strcat(temp, src); return strstr(temp, target) != NULL ? 1 : 0; } // 主函数：完整测试 int main() { // 测试左旋 char str_rotate[1000]; int rotate_n; printf("===== 测试字符串左旋 =====\n"); printf("请输入待旋转的字符串："); fgets(str_rotate, sizeof(str_rotate), stdin); str_rotate[strcspn(str_rotate, "\n")] = '\0'; printf("请输入旋转位数："); scanf("%d", &rotate_n); getchar(); leftRotate(str_rotate, rotate_n); printf("左旋%d位后的结果：%s\n\n", rotate_n, str_rotate); // 测试判断旋转 char src[1000], target[1000]; printf("===== 测试判断旋转字符串 =====\n"); printf("请输入原字符串："); fgets(src, sizeof(src), stdin); src[strcspn(src, "\n")] = '\0'; printf("请输入目标字符串："); fgets(target, sizeof(target), stdin); target[strcspn(target, "\n")] = '\0'; int flag = isRotateString(src, target); printf("目标字符串是否是原字符串的旋转结果：%s\n", flag ? "是" : "否"); return 0; }