踩坑实录从 “越写越乱” 到 “一行核心逻辑”我搞定了字符串旋转问题今天刷题时我接连遇到两道字符串旋转相关的题一个是实现字符串左旋另一个是判断一个字符串是否是另一个的旋转结果。本来以为是小问题结果代码越改越长踩了一堆坑。折腾了大半天终于从暴力模拟转向了优雅解法记录一下这个 “拨乱反正” 的过程。最初的暴力思路代码越写越臃肿第一步实现字符串左旋从打印到生成最开始我想的是 “暴力模拟旋转”把字符串分成前 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 (p2p1) { 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; }不仅逻辑绕还出现了 “n0 时返回失败” 的 bug—— 其实 n0 时旋转结果就是原字符串应该返回成功。第二步判断旋转字符串暴力枚举所有可能有了生成旋转字符串的函数我想的是 “遍历所有旋转位数生成结果后逐一对比”于是封装了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一定是s1s1的子串。比如s1AABCD→s1s1AABCDAABCDs2BCDAA正好是其中的子串。用这个思路重写判断函数代码直接极简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; }踩坑总结从暴力到巧解的思维转变不要盲目模拟遇到 “旋转”“移动” 类问题先别急着暴力模拟想想 “反转”“拼接” 这类更高效的思路。边界处理要严谨空指针、空字符串、旋转位数越界用n%len处理是字符串问题的高频坑。函数解耦很重要把左旋和判断旋转拆成独立函数代码复用性更高也更容易排查问题。时间空间复杂度要敏感暴力法 O (n²) 的效率在数据量大时会直接超时而巧解能把时间复杂度降到 O (n)。
