將 Java 字串旋轉 n 個字符
1. 概述
在我們日常的Java程式設計中,字串往往是我們必須處理的基本物件。有時,我們需要將給定的字串旋轉n
字元。旋轉字串涉及以循環方式移動其字符,從而創建動態且具有視覺吸引力的效果。
在本教程中,我們將探索解決字串旋轉問題的不同方法。
2.問題介紹
當我們說將字串旋轉n
字元時,意味著在字串中移動n
字元。舉個例子可以幫助我們快速理解問題。
2.1.一個例子
假設我們有一個字串物件:
String STRING = "abcdefg";
如果我們採用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
...
上面的範例說明了向前字串旋轉的行為。然而,繩子也可以向相反方向旋轉——向後旋轉,如下圖所示:
- 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
...
在本教程中,我們將探討向前和向後旋轉。我們的目標是創建一種能夠透過移動n
字元來沿指定方向旋轉輸入字串的方法。
為了簡單起見,我們將限制我們的方法只接受n
的非負值。
2.2.分析問題
在深入研究程式碼之前,讓我們先分析這個問題並總結其關鍵特徵。
首先,如果我們透過移位零(n=0)
個字元來旋轉字串,無論方向如何,結果都應該鏡像輸入字串。這本質上是清楚的,因為當n
等於0
時不會發生旋轉。
此外,如果我們看一下這個例子,當n=7,
輸出再次等於輸入:
Input String : abcdefg
...
Rotate (n = 7) -> abcdefg
...
出現這種現像是因為輸入字串的長度是7
。當n
等於STRING.length,
每個字元在旋轉後會回到原始位置。因此,透過移位STRING.length
字元來旋轉STRING
的結果與原始STRING.
現在,很明顯,當n = STRING.length × K
(其中K
是整數)時,輸入和輸出字串相等。簡單來說,移位字元的有效n'
本質上是n % STRING.length
。
接下來,讓我們來看看旋轉方向。透過比較前面提供的向前和向後旋轉的範例,可以看出「向後旋轉n
」本質上等同於「向前旋轉STRING.length – n
」 。例如, n=2
向後旋轉與n=5 (STRING.length – 2)
的向前旋轉產生相同的結果,如下所示:
- Forward Rotation -
Rotate (n = 5) -> cdefgab
...
- Backward Rotation -
Rotate (n = 2) -> cdefgab
...
所以,我們只能集中精力解決正向旋轉問題,將所有反向旋轉轉換為正向旋轉。
讓我們簡要地列出到目前為止我們學到的內容:
- 有效
n' = n % STRING.length
-
n=0 or K × STRING.length
:result = STRING
- “向後旋轉
n”
可以轉換為“向前旋轉(STRING.length – n)”
2.3.準備測試數據
由於我們將使用單元測試來驗證我們的解決方案,因此讓我們建立一些預期輸出來涵蓋各種場景:
// 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";
接下來,讓我們轉向第一個解決方案,「拆分和合併」。
3. 拆分與合併
解決該問題的想法是將輸入字串拆分為兩個子字串,然後交換它們的位置並重新組合它們。像往常一樣,一個例子將幫助我們快速理解這個想法。
假設我們想要透過移動兩個 ( n=2
) 個字元來向前旋轉STRING
。然後,我們可以透過以下方式進行旋轉:
Index 0 1 2 3 4 5 6
STRING abcdefg
Sub1 [abcde] -->
Sub2 <-- [fg]
Result [fg] [abcde]
因此,解決問題的關鍵是找到兩個子字串的索引範圍。這對我們來說不是一個挑戰:
- Sub 1 –
[0, STRING.length – n),
在本例中為[0,5)
- Sub 2 –
[STRING.length – n, STRING.length)
在本例中為[5, 7)
值得注意的是,上面使用的半開符號「 [a, b)
」表示索引「 a
」是包含的,而「 b
」是排除的。有趣的是, Java 的String.subString(beginIndex, endIndex)
方法恰好遵循排除endIndex
的相同約定,從而簡化了索引計算。
現在,根據我們的理解,實現變得簡單:
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);
}
如所觀察到的, boolean
變數forward
表示預期旋轉的方向。隨後,我們使用表達式「 n = forward ? n : len – n
” 將向後旋轉無縫轉換為向前旋轉。
此外,該方法成功通過了我們準備的測試案例:
// 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. 自連接和提取
這種方法的本質在於將字串與其自身連接起來,創建SS = STRING + STRING
。因此,無論我們如何旋轉原始STRING,
結果字串都必須是SS
的子字串。因此,我們可以有效地定位SS
中的子字串並提取它。
例如,如果我們以n=2
向前旋轉STRING
,結果為SS.subString(5,12)
:
Index 0 1 2 3 4 5 6 | 7 8 9 10 11 12 13
SS abcdefg | abcdefg
|
Result abcde [fgabcde] fg
現在,問題轉變為識別自連接字串SS
中預期的開始和結束索引。這個任務對我們來說相對簡單:
- 起始索引:
STRING.length – n
- 結束索引:
StartIndex + STRING.length = 2 × STRING.length – n
接下來,我們將這個想法「翻譯」成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);
}
這個方法也通過了我們的測試:
// 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));
所以,它解決了我們的字串旋轉問題。
我們已經知道STRING
的旋轉結果將是SS
的子字串。值得注意的是,我們可以使用此規則來檢查一個字串是否從另一個字串旋轉:
boolean rotatedFrom(String rotated, String rotateFrom) {
return rotateFrom.length() == rotated.length() && (rotateFrom + rotateFrom).contains(rotated);
}
最後,讓我們快速測試一下該方法:
assertTrue(rotatedFrom(EXPECT_7X, STRING));
assertTrue(rotatedFrom(B_EXPECT_3X, STRING));
assertFalse(rotatedFrom("abcefgd", STRING));
5. 結論
在本文中,我們首先分析了將字串旋轉n
字元的問題。然後,我們探索了兩種不同的方法來解決這個問題。
與往常一樣,範例的完整原始程式碼可在 GitHub 上取得。