在这篇文章中，我们将深入探讨一个非常经典且在面试中高频出现的字符串问题：如何判断一个字符串是否是另一个字符串的旋转版本。这听起来像是一个简单的操作，但它背后隐藏着关于字符串操作、算法效率以及编程技巧的深刻见解。我们将一起从最基本的暴力方法开始，逐步探索更优雅的解决方案，并分析每种方法的优劣。无论你是准备技术面试，还是想在日常编码中提升性能，这篇文章都将为你提供实用的知识。
问题描述与核心概念
首先，让我们明确一下问题的定义。给定两个长度相等的字符串 s1 和 s2，我们的任务是确定 s2 是否可以通过旋转 s1 得到。
什么是“旋转”？
想象一下，你手中拿着一根绳子，上面串着一串字符。如果你抓住绳子的两端，将一部分字符从头部移到尾部（或者从尾部移到头部），这就形成了一次“旋转”。具体来说，如果不改变字符的相对顺序，仅通过将原字符串的前导字符移动到末尾（或反之）来获得新字符串，那么我们就说这两个字符串互为旋转。
为了让你更直观地理解，让我们来看几个具体的例子：
示例 1：
> 输入： s1 = "abcd", s2 = "cdab"
> 输出： true
> 解释： 让我们看看发生了什么。我们可以将 s1 的前两个字符 "ab" 移动到末尾，这相当于向左旋转 2 次。或者，我们也可以将 "cd" 移到前面。无论哪种方式，s2 都是 s1 的旋转。
示例 2：
> 输入： s1 = "aab", s2 = "aba"
> 输出： true
> 解释： 这里我们将 s1 的第一个字符 ‘a‘ 移动到末尾，它就变成了 s2。
示例 3：
> 输入： s1 = "abcd", s2 = "acbd"
> 输出： false
> 解释： 在这个例子中，无论你怎么旋转 s1，都不可能得到 s2，因为 ‘c‘ 和 ‘b‘ 的相对顺序发生了改变。旋转操作保持字符的循环顺序不变。
方法一：朴素方法 – 生成所有旋转
核心思路：
既然旋转意味着字符的循环移动，最直接的想法就是：让我们模拟所有的旋转过程，看看是否有一步能匹配上目标字符串。
对于长度为 n 的字符串，它本质上只有 n 种可能的旋转状态（包括它本身）。我们可以编写一个循环，每一次迭代都将字符串旋转一次（例如，将最后一个字符移到最前面），然后立即检查它是否等于 s2。如果我们尝试了所有 n 次旋转都没有匹配，那么答案就是 false。
复杂度分析：
这种方法虽然直观，但效率并不高。
- 时间复杂度：O(n²)。我们在外层循环 n 次，而在每次循环中，进行字符串拼接或字符移动的操作通常需要 O(n) 的时间（因为字符串通常是不可变的，修改意味着创建副本）。因此，总的时间复杂度是 O(n²)。
- 空间复杂度：O(1)。如果我们直接在原字符串上操作（仅限于 C/C++ 等支持原地修改的语言），或者只使用了常数级别的额外空间。
尽管这不是最快的方法，但理解它对于我们掌握字符串的特性至关重要。下面是这种方法在不同编程语言中的具体实现，我都为你添加了详细的中文注释。
#### C++ 实现
在 C++ 中，我们可以直接修改传入的字符串引用（如果允许的话），利用 pop_back 和字符串拼接来模拟旋转。
#include
using namespace std;
// 检查 s2 是否是 s1 的旋转
bool areRotations(string &s1, string &s2) {
int n = s1.size();
// 边界条件：长度必须相等
if (n != s2.size()) return false;
// 外层循环：生成并检查 s1 的所有可能旋转
for (int i = 0; i < n; ++i) {
// 如果当前旋转等于 s2，说明找到了匹配，返回 true
// 注意：第一次循环检查的是原始字符串
if (s1 == s2)
return true;
// 执行向右旋转操作：将最后一个字符移到最前面
char last = s1.back();
s1.pop_back(); // 移除最后一个字符
s1 = last + s1; // 将其加到最前面
}
return false;
}
int main() {
string s1 = "aab";
string s2 = "aba";
// 输出结果
cout << (areRotations(s1, s2) ? "true" : "false");
return 0;
}
#### C 语言实现
C 语言的处理方式略有不同，因为我们需要手动管理字符数组。这里我们使用一个循环来手动移动字符。
#include
#include
#include
bool areRotations(char s1[], char s2[]) {
int n = strlen(s1);
if (n != strlen(s2)) return false;
// 生成并检查 s1 的所有可能旋转
for (int i = 0; i 0; j--) {
s1[j] = s1[j-1];
}
// 3. 将保存的最后一个字符放到开头
s1[0] = last;
}
return false;
}
int main() {
char s1[] = "aab";
char s2[] = "aba";
printf("%s", areRotations(s1, s2) ? "true" : "false");
return 0;
}
#### Java 实现
在 Java 中，String 是不可变的，所以 s1 = last + s1.substring(...) 实际上创建了一个新的 String 对象。这使得代码非常简洁，但在底层涉及到内存的分配。
class GfG {
static boolean areRotations(String s1, String s2) {
int n = s1.length();
if (n != s2.length()) return false;
// 生成并检查 s1 的所有可能旋转
for (int i = 0; i < n; ++i) {
// 使用 equals 方法检查内容是否相等
if (s1.equals(s2)) {
return true;
}
// 向右旋转 s1
// 取出最后一个字符，拼接到截取后的子字符串前面
char last = s1.charAt(s1.length() - 1);
s1 = last + s1.substring(0, s1.length() - 1);
}
return false;
}
public static void main(String[] args) {
String s1 = "aab";
String s2 = "aba";
System.out.println(areRotations(s1, s2));
}
}
#### Python 实现
Python 的切片功能让字符串操作变得异常简洁。INLINECODE91a42ffc 获取最后一个字符，INLINECODEc0f15c69 获取除最后一个字符外的所有字符。
def areRotations(s1, s2):
n = len(s1)
if n != len(s2): return False
# 生成并检查 s1 的所有可能旋转
for _ in range(n):
# 直接比较内容
if s1 == s2:
return True
# 向右旋转 s1
# 利用切片特性，一步到位
s1 = s1[-1] + s1[:-1]
return False
if __name__ == "__main__":
s1 = "aab"
s2 = "aba"
print("true" if areRotations(s1, s2) else "false")
#### C# 实现
C# 的字符串处理方式与 Java 类似，利用 Substring 方法和字符索引来构建新的旋转字符串。
using System;
class GfG {
static bool areRotations(string s1, string s2) {
int n = s1.Length;
if (n != s2.Length) return false;
// 生成并检查 s1 的所有可能旋转
for (int i = 0; i < n; ++i) {
// C# 中 == 运算符已被重载，用于比较字符串内容
if (s1 == s2) {
return true;
}
// 向右旋转 s1
char last = s1[s1.Length - 1];
s1 = last + s1.Substring(0, s1.Length - 1);
}
return false;
}
static void Main() {
string s1 = "aab";
string s2 = "aba";
Console.WriteLine(areRotations(s1, s2) ? "true" : "false");
}
}
#### JavaScript 实现
JavaScript 同样提供了便捷的字符串方法。注意这里的 s1 变量在循环中被重新赋值。
function areRotations(s1, s2) {
let n = s1.length;
if (n !== s2.length) return false;
// 生成并检查 s1 的所有可能旋转
for (let i = 0; i < n; i++) {
// 严格相等检查
if (s1 === s2) {
return true;
}
// 向右旋转 s1
s1 = s1[s1.length - 1] + s1.substring(0, s1.length - 1);
}
return false;
}
// 测试用例
let s1 = "aab";
let s2 = "aba";
console.log(areRotations(s1, s2) ? "true" : "false");
实战经验与常见错误
作为开发者，我们在处理类似问题时，往往会遇到一些坑。让我根据多年的经验分享几点心得。
常见错误 1：忽略长度检查
在上面的代码中，为了保持与原始逻辑的一致性，我们主要关注旋转逻辑本身。但在实际生产环境中，第一步必须检查长度。如果 s1 和 s2 长度不同，它们绝对不可能是旋转关系。尽早返回 false 可以节省大量的计算资源。
常见错误 2：空字符串的处理
两个空字符串算不算旋转？通常来说，算的。我们的循环逻辑中，如果 n=0，循环不执行，返回 false。但在业务逻辑上，你可能需要专门处理 if (n == 0) return true; 的情况，视具体需求而定。
性能优化建议
虽然朴素方法在小数据量下表现尚可，但在处理长文本（比如 DNA 序列分析或大日志处理）时，O(n²) 的复杂度是致命的。
- 利用队列： 实际上，旋转字符串就像是在操作队列。将 s1 视为一个双端队列，我们可以利用高性能的队列数据结构来优化移动操作。
- 避免频繁内存分配： 在 C++ 或 Java 中，频繁创建新的字符串对象会导致内存碎片化。如果允许，尝试在字符数组级别进行操作，或者考虑我们即将提到的更高级的算法。
更好的解决方案：拼接字符串法
虽然我们在本文中主要展示了朴素方法的代码，但我必须向你推荐一个时间复杂度为 O(n) 的更优解法，这也是面试官真正期待的答案。
思路：
如果 s2 是 s1 的旋转，那么 s2 一定是 s1 + s1（将 s1 拼接到它自身后面）的子串。
例如：
- s1 = "abcd"
- s1 + s1 = "abcdabcd"
- 如果 s2 = "cdab"，我们可以发现 "cdab" 确实出现在 "abcdabcd" 中。
为什么这有效？
因为 s1 的所有旋转状态都会完整地包含在 s1+s1 这个长字符串中。这种方法将问题转化为一个“子串查找”问题，可以使用 KMP 算法或标准库中的 INLINECODEe3315ab4/INLINECODE8bd88f0e 函数来解决，效率极高。
总结与后续步骤
在这篇文章中，我们通过“生成所有旋转”这一朴素方法，深入探讨了字符串旋转检测的原理。我们不仅学习了如何在 C++、Java、Python、C# 和 JavaScript 中实现这一逻辑，更重要的是，我们理解了算法背后的时间与空间成本。
关键要点：
- 旋转保持字符的相对循环顺序。
- 朴素方法直观易懂，通过模拟物理旋转过程来解题，适用于理解问题。
- 在生产代码中，始终记得先进行边界检查（如长度比较）。
- 性能敏感场景下，请考虑使用“拼接字符串法”或 KMP 算法。
你的下一步：
我建议你亲手在编辑器中敲一遍上面的代码（不仅仅是复制粘贴），并尝试修改输入来观察输出。然后，尝试实现我们最后提到的“拼接字符串法”，对比一下代码的简洁度和运行速度。这种对比学习将极大地加深你对算法的理解。
祝你在编码之路上越走越远，如果你有任何疑问或想分享你的见解，欢迎随时交流！