《剑指offer》之左旋字符串

判断一个字符串是否为另外一个字符串旋转之后的字符串。

输入示例：输入字符串s1 和 s2, 并且会输入移动位数。

例如：给定 s1 =AABCD 和 s2 = BCDAA，返回1

给定s1=abcd和s2=ACBD，返回0.

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

AABCD右旋一个字符得到DAABC

方法一

       一个一个移动，判断是否相同。

#include <stdio.h> #include <string.h> int Find(char* str1, char* str2) { int flag = 0;//判断是否为左旋字符串 int len = strlen(str1); int i = 0, j = 0; for (i = 0; i < len; i++) { char tmp = str1[0]; for (j = 0; j < len - 1; j++) { str1[j] = str1[j + 1]; } str1[j] = tmp; if (strcmp(str1, str2) == 0) { flag = 1; break; } } return flag; } int main() { char str1[10]; char str2[10]; gets(str1); gets(str2); int flag = Find(str1, str2); if (flag) { printf("是左旋后的字符串\n"); } else { printf("不是\n"); } return 0; } 方法二

       使用库函数 strcpy 和 strncat；将 str1 后半部分 拷贝到arr1 里面，再将 str1 的前半部分拼接到 arr1 里面，最后判断 arr1 是否和 str2 一致即可。

#include <stdio.h> #include <string.h> int main() { char str1[10]; char str2[10]; char arr1[20]; gets(str1); gets(str2); int n; scanf("%d", &n);//输入左移几位 int len = strlen(str1); int k = n % len; //实际移动位数 strcpy(arr1, str1 + k);//将str1后半部分 拷贝到arr1里面 strncat(arr1, str1, k); //将str1 的前半部分拼接到arr1里面 if (strcmp(arr1, str2) == 0) { printf("是旋转后的字符串\n"); } else { printf("不是\n"); } return 0; } 方法三

       三段翻转：

#include <stdio.h> #include <string.h> void reverse(char* p, int str, int end) { char tmp = p[str]; for (int i = str; i < end; i++) { p[i] = p[i + 1]; } p[end] = tmp; } int main() { char str1[10]; char str2[10]; gets(str1); gets(str2); int len = strlen(str1); int n; scanf("%d", &n); reverse(str1, 0, n - 1); reverse(str1, n - 1, len - 1); reverse(str1, 0, len - 1); if (strcmp(str1, str2) == 0) { printf("是旋转后的字符串\n"); } else { printf("不是\n"); } return 0; }