本篇总结了字符串旋转问题的几种解决方法，字符串左旋和右旋原理相同，会其一便可知其二，当然还有很多方法，我只列举相对容易理解的方法。
左旋转字符串
字符串旋转问题：字符串左旋
实现一个函数，可以左旋字符串中的k个字符。 例如： ABCD左旋一个字符得到BCDA ABCD左旋两个字符得到CDAB
方法1：暴力旋转法
每次让字符串旋转一个，然后让旋转几个就循环几次。
思路：
1.拿走第一个字符
2.让数组后面的字符往前覆盖
3.让最后一个元素放入第一个字符
#include <string.h> void left_move(char arr[], int k) { int len = strlen(arr); k %= len;//当字符旋转次数为自己长度时，字符旋转跟没有旋转一样，（也就旋转回来了） //所以超过自身次数旋转跟某次旋转是一样的 //第一步拷贝拿走第一个字符 char tmp = arr[0]; //第二步，将后面的往前覆盖 int i; for (i = 0; i < len - 1; i++) { arr[i] = arr[i + 1]; } //第三步，将第一个字符放在最后面 arr[len - 1] = tmp; } int main() { char arr[] = "ABCD"; int k; scanf("%d", &k); left_move(arr, k); printf("%s", arr); return 0; }
方法2：空间辅助法
借助一个数组让它帮忙先放下不着急旋转的字符串，然后再将要旋转的字符放在后面，最后再拷贝回来
思路：
1.创建一个数组空间
2.将不旋转的字符串先放进去
3.将要旋转的字符放在后面
4.将数组拷贝回来
void left_move(char arr[],int k) { //1.创建一个空数组 char tmp[256] = { 0 }; //旋转k 这个点是一个断点k后面的是不旋转的字符串，前面是旋转的字符 //后面不旋转的拷贝到tmp中， strcpy(tmp, arr + k); //再将前面旋转的放进tmp后面 strncat(tmp, arr, k);// strncat功能： 将arr中k个字符追加到tmp后面 //再将tmp拷贝回去 strcpy(arr, tmp); } int main() { char arr[] = "abcdef"; int k; scanf("%d", &k); left_move(arr,k) printf("%s", arr); return 0; }
方法3：三步翻转法
对于这个方法我们可以这样想：
将一个字符串分成两个部分，X和Y两个部分，在字符串上定义反转（逆序）的操作为
X^T, 即把X的所有字符全部反转（逆序）【比如X=“abcd”,全部反转为 “dcba”,所以X ^T=“dcba”】，那么我们可以得到下面的结论：
(X ^T Y ^T) ^T=YX.
所以显然就可以转换为字符串反转的问题了
思路也就是：
第一步逆序左边（k处为分界点）
第二步逆序右边
第三步逆序整体
void reverse(char *left,char*right) { //逆序函数需要两个指针分别指向前面和后面，当前面指针小于后面指针时 //说明还有元素需要逆序 while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } int main() { char arr[] = "ABCD"; int len = strlen(arr); int k=0; scanf("%d", &k); int k%=len; //写一个逆序函数reserve //先逆序左边 reverse(arr,arr+k-1); //再逆序右边 reverse(arr + k, arr + len - 1); //再整体逆序 reverse(arr, arr + len - 1); printf("%s", arr); return 0; }
结果：
字符串旋转结果
写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。 例如：给定s1 =AABCD和s2 = BCDAA，返回1 给定s1=abcd和s2=ACBD，返回0. AABCD左旋一个字符得到ABCDA AABCD左旋两个字符得到BCDAA AABCD右旋一个字符得到DAABC
这个也是字符串旋转问题，要求判断一个字符串是否是另外一个字符串旋转得到的
方法1：利用左旋字符串函数判断
思路：
我们可以利用上面的左旋字符的函数，让一个字符串每次旋转一次，每次旋转完后再与另外一个字符串比较，看是否相同。
当然有要注意的地方，当两个字符串长度都不一样大时，肯定不可能是旋转得到的。
#include <string.h> void left_move(char arr[], int k) { int len = strlen(arr); k %= len;//当字符旋转次数为自己长度时，字符旋转跟没有旋转一样，所以超过自身次数旋转跟某次旋转是一样的 //左旋字符串 //第一步拷贝拿走第一个字符 char tmp = arr[0]; //第二步，将后面的往前覆盖 int i; for (i = 0; i < len - 1; i++) { arr[i] = arr[i + 1]; } //第三步，将第一个字符放在最后面 arr[len - 1] = tmp; } int is_move(char arr1[], char arr2[]) { int len1 = strlen(arr1); int len2 = strlen(arr2); if (len1 != len2)//判断一下长度是否相等，如果不等直接返回0 { return 0; } int i; for (i = 0; i < len1; i++) { left_move(arr1, 1);//每次左旋一个 if (strcmp(arr1, arr2) == 0)//每次旋转完与字符串2比较是否相同 { return 1; } } return 0; } int main() { char arr1[] = "ABCDEF"; char arr2[] = "CDEFAB"; int ret=is_move(arr1, arr2); if (ret == 1) { printf("Yes\n"); } else { printf("No\n"); } }
方法2：空间辅助法
其实ABCDE无论怎么旋，旋转后的所有结果，都包含在了ABCDEABCD这个字符串里了。
所以做法很简单，只需要将原字符串再来一遍接在后面，然后找一找待查找的字符串是不是两倍原字符串的子集即可。
思路：
1.给字符串1自己追加一个自己字符串，然后拷贝到一个数组里
2.在追加后的字符串中找子符串中是否有与要比较的字符一样的
int is_move(char arr1[],char arr2[]) { int len1 = strlen(arr1); int len2 = strlen(arr2); if (len1 != len2)//判断一下长度是否相等，如果不等直接返回0 { return 0; } char tmp[256]={0};//用一个辅助空间将原字符串做成两倍原字符串 tmp=arr1;//将arr1中的内容拷贝到数组tmp中，因为tmp中空间足够大，可以给后面再追加len1个元素，因为arr1数组空间大小不知道，所有我们不能直接给arr1，追加自身字符。 strncat(tmp, arr1, len1);//给数组tmp追加一个arr1，追加6个元素 //strstr是用来查找字符串中的子串的，如果字符串中找到要比较的字符串 //那么将返回要比较的字符在该字符串中的地址 //如果没有则返回NULL. if (strstr(tmp, arr2) != NULL) return 1; else return 0; } int main() { char arr1[] = "ABCDEF"; char arr2[] = "CDEFAB"; int ret = is_move(arr1, arr2); if (ret == 1) { printf("Yes\n"); } else { printf("No\n"); } return 0; }
结果：
