C语言字符串旋转问题的深入讲解

C语言字符串旋转问题的深入讲解

背景

字符串旋转指的是在不改变字符串的字母顺序的情况下，将字符串中的某几个字符移动到字符串的开头或结尾。字符串旋转问题是一种高频面试题，考查了面试者对于数组操作、数据结构算法、指针运算等多方面知识的掌握程度。

问题描述

给定一个字符串 s 和一个非负整数 n，将字符串中的前 n 个字符移到尾部。

解决方案

1. 暴力枚举

暴力枚举是一种直接且朴素的方法，即不断地取出字符串的第一个字符，然后将其追加到字符串末尾，重复这个过程 n 次，即可得到字符串旋转后的结果。

示例 1: 将字符串 "abcdefg" 中的前 2 个字符旋转到字符串结尾，得到旋转后的结果 "cdefgab"。

void rotateString(char* s, int n) {
    int len = strlen(s);
    char temp;
    while (n--) {
        temp = s[0];
        for (int i = 0; i < len - 1; i++) {
            s[i] = s[i + 1];
        }
        s[len - 1] = temp;
    }
}

2. 三次反转法

数学家 Juggling 于 1984 年提出了一种更为高效的方法，被称为“三次反转法”。具体地，我们可以将字符串分为两个子串：前 n 个字符和剩余字符。然后分别反转这两个子串，最后再将整个字符串反转，即可得到字符串旋转后的结果。通过这种方式，我们只需要进行 3 次反转操作就能完成字符串旋转，极大地提升了算法效率。

示例 2： 将字符串 "abcdefg" 中的前 2 个字符旋转到字符串结尾，得到旋转后的结果 "cdefgab"。

void reverse(char* s, int start, int end) {
    char temp;
    while (start < end) {
        temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
}

void rotateString(char* s, int n) {
    int len = strlen(s);
    n %= len;
    reverse(s, 0, n - 1);
    reverse(s, n, len - 1);
    reverse(s, 0, len - 1);
}

总结

字符串旋转问题是一类经典的算法问题，常见于笔试和面试等场合。本文介绍了两种求解方法：暴力枚举和三次反转法。其中暴力枚举方法简单直接，容易理解和实现，但时间复杂度为 $O(n^2)$，适用于 n 比较小的情况。而三次反转法则更为高效，时间复杂度为 $O(n)$，适用于 n 比较大的情况。通过本文的介绍，相信读者可以更好地掌握字符串旋转问题的求解技巧。