1. Overview
1.概述
In our daily Java programming, strings are often the fundamental objects we must handle. Sometimes, we need to rotate a given string by n characters. Rotating a string involves shifting its characters in a circular manner, creating a dynamic and visually engaging effect.
在日常 Java 编程中，字符串通常是我们必须处理的基本对象。有时，我们需要将给定的字符串旋转 n 个字符。旋转字符串涉及以循环方式移动字符，从而产生一种动态的视觉效果。
In this tutorial, we’ll explore different ways to solve the string rotation problem.
在本教程中，我们将探索解决字符串旋转问题的不同方法。
2. Introduction to the Problem
2.问题介绍
When we say rotating a string by n characters, it means shifting n characters in the string. An example can help us understand the problem quickly.
当我们说将字符串旋转n个字符时，意思是移动字符串中的n个字符。一个例子可以帮助我们快速理解这个问题。
2.1. An Example
2.1.示例
Let’s say we have a string object:
假设我们有一个字符串对象：
String STRING = "abcdefg";If we take STRING as the input, after rotating it n characters, the results will be the following:
如果将 STRING 作为输入，旋转 n 个字符后，结果如下：
- Forward Rotation -
Input String : abcdefg
Rotate (n = 1) -> gabcdef
Rotate (n = 2) -> fgabcde
Rotate (n = 3) -> efgabcd
Rotate (n = 4) -> defgabc
Rotate (n = 5) -> cdefgab
Rotate (n = 6) -> bcdefga
Rotate (n = 7) -> abcdefg
Rotate (n = 8) -> gabcdef
...
The example above illustrates the behavior of forward string rotation. However, the string can also be rotated in the opposite direction—backward rotation, as depicted below:
上例说明了弦向前旋转的情况。不过，字符串也可以反向旋转，如下图所示：
- Backward Rotation -
Input String : abcdefg
Rotate (n = 1) -> bcdefga
Rotate (n = 2) -> cdefgab
Rotate (n = 3) -> defgabc
Rotate (n = 4) -> efgabcd
Rotate (n = 5) -> fgabcde
Rotate (n = 6) -> gabcdef
Rotate (n = 7) -> abcdefg
...
In this tutorial, we’ll explore both forward and backward rotations. Our objective is to create a method capable of rotating an input string in a specified direction by shifting n characters.
在本教程中，我们将探讨正向和反向旋转。我们的目标是创建一个方法，通过移动 n 字符，将输入字符串按指定方向旋转。
To keep things simple, we’ll limit our method to accepting only non-negative values for n.
为了简单起见，我们将限制我们的方法只接受 n 的非负值。
2.2. Analyzing the Problem
2.2.分析问题
Before we dive into the code, let’s analyze this problem and summarize its key characteristics.
在深入研究代码之前，我们先来分析一下这个问题，总结一下它的主要特点。
First, if we rotate the string by shifting zero (n=0) characters, irrespective of the direction, the result should mirror the input string. This is inherently clear since no rotation occurs when n equals 0.
首先，如果我们通过移动 0 个(n=0)字符来旋转字符串，无论方向如何，结果都应与输入字符串一致。这一点本身就很清楚，因为当 n 等于 0 时，不会发生旋转。
Furthermore, if we look at the example, when n=7, the output equals the input again:
此外，如果我们看一下示例，当 n=7 时， 输出再次等于输入：
Input String : abcdefg
...
Rotate (n = 7) -> abcdefg
...
This phenomenon arises because the length of the input string is 7. When n equals STRING.length, each character returns to its original position after the rotation. Consequently, the result of rotating STRING by shifting STRING.length characters is identical to the original STRING.
出现这种现象的原因是输入字符串的长度为 7。当 n 等于 STRING.length 时， 旋转后每个字符都会返回到原来的位置。因此，通过移动 STRING.length 字符旋转 STRING 的结果与原始 STRING. 相同。
Now, it becomes evident that when n = STRING.length × K (where K is an integer), the input and output strings are equal. In simpler terms, the effective n’ to shift characters is essentially n % STRING.length.
现在，当n = STRING.length × K（其中K为整数）时，输入和输出字符串相等。简单地说，移位字符的有效 n’ 基本上是 n % STRING.长度。
Next, let’s look at the rotation directions. Upon comparing the forward and backward rotation examples provided earlier, it shows that “backward rotation with n” is essentially equivalent to “forward rotation with STRING.length – n“. For instance, a backward rotation with n=2 yields the same result as a forward rotation with n=5 (STRING.length – 2), as illustrated below:
接下来，我们来看看旋转方向。通过比较前面提供的正向和反向旋转示例，可以发现 “以 n进行反向旋转 “本质上等同于 “以STRING.length – n进行正向旋转”。例如，如下图所示，n=2 的后向旋转与 n=5 (STRING.length – 2) 的前向旋转产生相同的结果：
- Forward Rotation -
Rotate (n = 5) -> cdefgab
...
- Backward Rotation -
Rotate (n = 2) -> cdefgab
...
So, we can only focus on solving the forward rotation problem and transform all backward rotations into forward ones.
因此，我们只能专注于解决正向旋转问题，并将所有后向旋转转化为正向旋转。
Let’s briefly list what we’ve learned so far:
让我们简要列举一下我们目前所学到的知识：
- The effective n’ = n % STRING.length
- n=0 or K × STRING.length: result = STRING
- “Backward rotation with n” can be transformed into “Forward rotation with (STRING.length – n)”
2.3. Preparing the Testing Data
2.3.准备测试数据
As we’ll use unit tests to verify our solutions, let’s create some expected output to cover various scenarios:
由于我们将使用单元测试来验证我们的解决方案，因此让我们创建一些预期输出来涵盖各种情况：
// forward
String EXPECT_1X = "gabcdef";
String EXPECT_2X = "fgabcde";
String EXPECT_3X = "efgabcd";
String EXPECT_6X = "bcdefga";
String EXPECT_7X = "abcdefg"; // len = 7
String EXPECT_24X = "efgabcd"; //24 = 3 x 7(len) + 3
// backward
String B_EXPECT_1X = "bcdefga";
String B_EXPECT_2X = "cdefgab";
String B_EXPECT_3X = "defgabc";
String B_EXPECT_6X = "gabcdef";
String B_EXPECT_7X = "abcdefg";
String B_EXPECT_24X = "defgabc";Next, let’s move to the first solution, “split and combine”.
接下来，我们来看第一种解决方案，即 “拆分与合并”。
3. Split and Combine
3.拆分和合并
The idea to solve the problem is to split the input string into two substrings, then exchange their position and recombine them. As usual, an example will help us to quickly understand the idea.
解决问题的思路是将输入字符串拆分成两个子串，然后交换它们的位置并重新组合。像往常一样，一个示例可以帮助我们快速理解这一思路。
Let’s say we want to forward rotate STRING by shifting two (n=2) characters. Then, we can perform the rotation in the following way:
假设我们要通过移动两个 (n=2) 字符来正向旋转 STRING 。那么，我们可以按以下方法进行旋转：
Index 0 1 2 3 4 5 6
STRING a b c d e f g
Sub1 [a b c d e] -->
Sub2 <-- [f g]
Result [f g] [a b c d e]
Therefore, the key to solving the problem is finding the index ranges of the two substrings. This isn’t a challenge for us:
因此，解决问题的关键在于找到两个子串的索引范围。这对我们来说并非难事：
- Sub 1 – [0, STRING.length – n), In this example, it’s [0,5)
- Sub 2 – [STRING.length – n, STRING.length) In this example, it’s [5, 7)
It’s worth noting that the half-open notation “[a, b)” employed above indicates that the index ‘a‘ is inclusive, while ‘b‘ is exclusive. Interestingly, Java’s String.subString(beginIndex, endIndex) method coincidentally follows the same convention of excluding the endIndex, simplifying index calculations.
值得注意的是，上面使用的半开放符号”[a, b)“表示索引”a“是包含的，而”b“是排他的。有趣的是，Java 的 String.subString(beginIndex, endIndex) 方法巧合地遵循了同样的约定，即不包括 endIndex ，从而简化了索引计算。
Now, building upon our understanding, the implementation becomes straightforward:
现在，基于我们的理解，实施变得简单明了：
String rotateString1(String s, int c, boolean forward) {
if (c < 0) {
throw new IllegalArgumentException("Rotation character count cannot be negative!");
}
int len = s.length();
int n = c % len;
if (n == 0) {
return s;
}
n = forward ? n : len - n;
return s.substring(len - n, len) + s.substring(0, len - n);
}As observed, the boolean variable forward indicates the direction of the intended rotation. Subsequently, we employ the expression “n = forward ? n : len – n” to seamlessly convert backward rotations into their forward counterparts.
正如我们所观察到的，布尔变量forward指示了预定旋转的方向。随后，我们使用表达式”n = forward ? n : len – n“将后向旋转无缝转换为前向旋转。
Furthermore, the method successfully passes our prepared test cases:
此外，该方法还成功通过了我们准备的测试案例：
// forward
assertEquals(EXPECT_1X, rotateString1(STRING, 1, true));
assertEquals(EXPECT_2X, rotateString1(STRING, 2, true));
assertEquals(EXPECT_3X, rotateString1(STRING, 3, true));
assertEquals(EXPECT_6X, rotateString1(STRING, 6, true));
assertEquals(EXPECT_7X, rotateString1(STRING, 7, true));
assertEquals(EXPECT_24X, rotateString1(STRING, 24, true));
// backward
assertEquals(B_EXPECT_1X, rotateString1(STRING, 1, false));
assertEquals(B_EXPECT_2X, rotateString1(STRING, 2, false));
assertEquals(B_EXPECT_3X, rotateString1(STRING, 3, false));
assertEquals(B_EXPECT_6X, rotateString1(STRING, 6, false));
assertEquals(B_EXPECT_7X, rotateString1(STRING, 7, false));
assertEquals(B_EXPECT_24X, rotateString1(STRING, 24, false));4. Selfjoin and Extract
4.自连接和提取
The essence of this approach lies in concatenating the string with itself, creating SS = STRING + STRING. Consequently, regardless of how we rotate the original STRING, the resulting string must be a substring of SS. Hence, we can efficiently locate the substring within SS and extract it.
这种方法的精髓在于将字符串与自身连接，创建 SS = STRING + STRING。因此，无论我们如何旋转原始STRING，生成的字符串都必须是SS的子串。因此，我们可以高效地在 SS 中找到该子串并将其提取出来。
For instance, if we forward rotate STRING with n=2, the result is SS.subString(5,12):
例如，如果我们正向旋转 STRING n=2，结果就是 SS.subString(5,12) ：
Index 0 1 2 3 4 5 6 | 7 8 9 10 11 12 13
SS a b c d e f g | a b c d e f g
|
Result a b c d e [f g a b c d e] f g
Now, the problem transforms into identifying the expected start and end indexes in the self-joined string SS. This task is relatively straightforward for us:
现在，问题转变为识别自连接字符串 SS 中的预期开始和结束索引。这项任务对我们来说相对简单：
- Start index: STRING.length – n
- End index: StartIndex + STRING.length = 2 × STRING.length – n
Next, let’s “translate” this idea into Java code:
接下来，让我们把这个想法 “翻译 “成 Java 代码：
String rotateString2(String s, int c, boolean forward) {
if (c < 0) {
throw new IllegalArgumentException("Rotation character count cannot be negative!");
}
int len = s.length();
int n = c % len;
if (n == 0) {
return s;
}
String ss = s + s;
n = forward ? n : len - n;
return ss.substring(len - n, 2 * len - n);
}This method passes our tests too:
这种方法也通过了我们的测试：
// forward
assertEquals(EXPECT_1X, rotateString2(STRING, 1, true));
assertEquals(EXPECT_2X, rotateString2(STRING, 2, true));
assertEquals(EXPECT_3X, rotateString2(STRING, 3, true));
assertEquals(EXPECT_6X, rotateString2(STRING, 6, true));
assertEquals(EXPECT_7X, rotateString2(STRING, 7, true));
assertEquals(EXPECT_24X, rotateString2(STRING, 24, true));
// backward
assertEquals(B_EXPECT_1X, rotateString2(STRING, 1, false));
assertEquals(B_EXPECT_2X, rotateString2(STRING, 2, false));
assertEquals(B_EXPECT_3X, rotateString2(STRING, 3, false));
assertEquals(B_EXPECT_6X, rotateString2(STRING, 6, false));
assertEquals(B_EXPECT_7X, rotateString2(STRING, 7, false));
assertEquals(B_EXPECT_24X, rotateString2(STRING, 24, false));So, it solves our string rotation problem.
因此，它解决了我们的字符串旋转问题。
We have learned STRING‘s rotation result will be a substring of SS. It’s worth noting that we can use this rule to check if a string is rotated from the other string:
我们已经知道 STRING 的旋转结果将是 SS 的子串。值得注意的是，我们可以使用这条规则来检查一个字符串是否从另一个字符串旋转而来：
boolean rotatedFrom(String rotated, String rotateFrom) {
return rotateFrom.length() == rotated.length() && (rotateFrom + rotateFrom).contains(rotated);
}Finally, let’s test the method quickly:
最后，让我们快速测试一下这个方法：
assertTrue(rotatedFrom(EXPECT_7X, STRING));
assertTrue(rotatedFrom(B_EXPECT_3X, STRING));
assertFalse(rotatedFrom("abcefgd", STRING));5. Conclusion
5.结论
In this article, we first analyzed the rotating a string by n characters problem. Then, we explored two different approaches to solving this problem.
在本文中，我们首先分析了通过 n 个字符旋转字符串的问题。然后，我们探讨了解决这一问题的两种不同方法。
As always, the complete source code for the examples is available over on GitHub.
与往常一样，这些示例的完整源代码可在 GitHub 上获取。