檢查兩個字串是否互相旋轉
1. 概述
在本教程中，我們將學習如何檢查一個字串是否是另一個字串的旋轉。
我們將簡要討論什麼是弦旋轉。然後，我們將研究一些透過程式碼洞察和複雜性分析來解決問題的演算法。
2. 弦旋轉簡介
在深入研究一些解決方案之前，我們先討論字串旋轉以及我們應該測試演算法的內容。
2.1.弦和弦旋轉
字串是原始字元的序列，在 Java 中，它包裝在String類別中。儘管兩個字串可能是不同的對象，但我們可以比較它們的內部字元並檢查例如它們是否相等或包含共同模式。
字串的旋轉是指包含相同字元但順序不同的字串。具體來說，一個或多個字元從原始位置移動。例如，字串“cdab”是“abcd”的旋轉。這可以分為兩個步驟：
-
abcd->dabc將最後一個d移至第一個位置 -
dabc->cdab將最後一個c移至第一個位置
這是透過從右側移動來完成的，但也可以從左側完成。
值得注意的是，我們可以說，如果兩個字串的長度不同，它們就不能是另一個字串的一次旋轉。
2.2.變數名稱
為了進行演示，我們始終將rotation稱為潛在的候選字串，以檢查它是否是origin的實際旋轉。
2.3.單元測試
我們只有兩種情況來測試字串是否是旋轉。值得注意的是，弦是其自身的旋轉。因此，我們可能還想測試這個極端情況。
3. 雙串中包含的旋轉
我們可以天真地認為，如果我們將原始字串加倍，在某個時刻，它將包含旋轉。我們可以直觀地想像一下：
3.1.演算法
該演算法很簡單：
boolean doubledOriginContainsRotation(String origin, String rotation) {
if (origin.length() == rotation.length()) {
return origin.concat(origin)
.contains(rotation);
}
return false;
}3.2.程式碼洞察
我們將原點與其自身連接起來，並檢查它是否包含潛在的旋轉：
return origin.concat(origin).contains(rotation);我們看一下演算法複雜度：
- 時間複雜度：O(n*m)，其中 n 是串聯長度，m 是旋轉長度
- 空間複雜度：O(n) 與字串的長度成正比
3.3.單元測試
當旋轉正常時，讓我們測試一下雙倍原始字串中包含的旋轉。我們還將測試原點何時是與旋轉完全相同的字串：
@Test
void givenDoubledOrigin_whenCheckIfOriginContainsRotation_thenIsRotation() {
assertTrue(doubledOriginContainsRotation("abcd", "cdab"));
assertTrue(doubledOriginContainsRotation("abcd", "abcd"));
}讓我們測試一下何時不包含旋轉。我們還將測試旋轉何時比原點更長：
@Test
void givenDoubledOrigin_whenCheckIfOriginContainsRotation_thenNoRotation() {
assertFalse(doubledOriginContainsRotation("abcd", "bbbb"));
assertFalse(doubledOriginContainsRotation("abcd", "abcde"));
}4. 從共同點開始旋轉
我們可以使用之前的方法並建立更詳細的演算法。
首先，我們收集原點起始字元旋轉中的所有索引。最後，我們循環原點並比較移動位置的字串。讓我們更詳細地描述這些步驟：
4.1.演算法
一旦我們知道了公共字符，我們就可以檢查字串是否繼續相等：
boolean isRotationUsingCommonStartWithOrigin(String origin, String rotation) {
if (origin.length() == rotation.length()) {
List<Integer> indexes = IntStream.range(0, origin.length())
.filter(i -> rotation.charAt(i) == origin.charAt(0))
.boxed()
.collect(Collectors.toList());
for (int startingAt : indexes) {
if (isRotation(startingAt, rotation, origin)) {
return true;
}
}
}
return false;
}
boolean isRotation(int startingAt, String rotation, String origin) {
for (int i = 0; i < origin.length(); i++) {
if (rotation.charAt((startingAt + i) % origin.length()) != origin.charAt(i)) {
return false;
}
}
return true;
}4.2.程式碼洞察
有兩個要點需要注意。第一個是我們收集索引的地方：
List<Integer> indexes = IntStream.range(0, origin.length())
.filter(i -> rotation.charAt(i) == origin.charAt(0))
.boxed()
.collect(Collectors.toList());這些是旋轉中我們可以找到原點起始字元的位置。
然後，我們循環遍歷字串並檢查移動的位置：
for (int i = 0; i < origin.length(); i++) {
if (rotation.charAt((startingAt + i) % origin.length()) != origin.charAt(i)) {
return false;
}
}值得注意的是，當超過旋轉長度時，我們使用模 (%) 從第一個索引返回。
我們看一下演算法複雜度：
- 時間複雜度：O(n*m)，其中 n 是原點的長度，m 是找到的索引的數量
- 空間複雜度：O(n)
4.3.單元測試
讓我們測試旋轉何時與原點具有共同的起始字元並且字串的其餘部分相等：
@Test
void givenOriginAndRotationInput_whenCheckingCommonStartWithOrigin_thenIsRotation() {
assertTrue(isRotationUsingCommonStartWithOrigin("abcd", "cdab"));
assertTrue(isRotationUsingCommonStartWithOrigin("abcd", "abcd"));
}讓我們測試一下旋轉何時具有共同的起始字符，但它要么太長，要么其餘部分不匹配：
@Test
void givenOriginAndRotationInput_whenCheckingCommonStartWithOrigin_thenNoRotation() {
assertFalse(isRotationUsingCommonStartWithOrigin("abcd", "bbbb"));
assertFalse(isRotationUsingCommonStartWithOrigin("abcd", "abcde"));
}5. 前後綴旋轉比較
如果我們找到原點和旋轉的共同起始字符，我們也可以說我們的字串在該匹配點之前和之後將相等。例如，我們的原始字串“ abcd”在位置2處與“cdab”有共同的c 。但是，對於字串的其餘部分，前綴和後綴需要相應地相等：
5.1.演算法
每當我們找到一個共同字元時，我們就可以比較剩餘字元段的前綴和後綴，反轉原點和旋轉：
boolean isRotationUsingSuffixAndPrefix(String origin, String rotation) {
if (origin.length() == rotation.length()) {
return checkPrefixAndSuffix(origin, rotation);
}
return false;
}
boolean checkPrefixAndSuffix(String origin, String rotation) {
if (origin.length() == rotation.length()) {
for (int i = 0; i < origin.length(); i++) {
if (origin.charAt(i) == rotation.charAt(0)) {
if (checkRotationPrefixWithOriginSuffix(origin, rotation, i)) {
if (checkOriginPrefixWithRotationSuffix(origin, rotation, i)) {
return true;
}
}
}
}
}
return false;
}
boolean checkRotationPrefixWithOriginSuffix(String origin, String rotation, int i) {
return origin.substring(i)
.equals(rotation.substring(0, origin.length() - i));
}
boolean checkOriginPrefixWithRotationSuffix(String origin, String rotation, int i) {
return origin.substring(0, i)
.equals(rotation.substring(origin.length() - i));
}5.2.程式碼洞察
我們有兩項檢查要做。首先，我們比較旋轉前綴和原點字尾：
return origin.substring(i)
.equals(rotation.substring(0, origin.length() - i));然後，我們將旋轉後綴與原點前綴進行比較：
return origin.substring(0, i)
.equals(rotation.substring(origin.length() - i));值得注意的是，這些檢查可以按任何順序進行。
我們看一下演算法複雜度：
- 時間複雜度：O(n*n) 比較兩個長度為 n 的字串
- 空間複雜度：O(n)
5.3.單元測試
讓我們測試旋轉何時具有與給定公共字元的原點相同的後綴和前綴：
@Test
void givenOriginAndRotationInput_whenCheckingUsingSuffixAndPrefix_thenIsRotation() {
assertTrue(isRotationUsingSuffixAndPrefix("abcd", "cdab"));
assertTrue(isRotationUsingSuffixAndPrefix("abcd", "abcd"));
}讓我們測試一下旋轉何時與原點不具有相同的後綴和前綴：
@Test
void givenOriginAndRotationInput_whenCheckingUsingSuffixAndPrefix_thenNoRotation() {
assertFalse(isRotationUsingSuffixAndPrefix("abcd", "bbbb"));
assertFalse(isRotationUsingSuffixAndPrefix("abcd", "abcde"));
}6. 字元隊列的旋轉比較
該問題的另一種觀點是將兩個字串想像為佇列。然後，我們將旋轉的頂部字元移到尾部，並將新佇列與原點進行比較。讓我們來看看隊列的簡單圖片：
6.1.演算法
我們創建兩個隊列。然後，我們從頂部字元移動到旋轉的底部，同時在每一步檢查它是否等於原點。
boolean isRotationUsingQueue(String origin, String rotation) {
if (origin.length() == rotation.length()) {
return checkWithQueue(origin, rotation);
}
return false;
}
boolean checkWithQueue(String origin, String rotation) {
if (origin.length() == rotation.length()) {
Queue<Character> originQueue = getCharactersQueue(origin);
Queue<Character> rotationQueue = getCharactersQueue(rotation);
int k = rotation.length();
while (k > 0 && null != rotationQueue.peek()) {
k--;
char ch = rotationQueue.peek();
rotationQueue.remove();
rotationQueue.add(ch);
if (rotationQueue.equals(originQueue)) {
return true;
}
}
}
return false;
}
Queue<Character> getCharactersQueue(String origin) {
return origin.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.toCollection(LinkedList::new));
}6.2.程式碼洞察
創建隊列後，相關的是我們如何斷言我們的字串是相等的：
int k = rotation.length();
while (k > 0 && null != rotationQueue.peek()) {
k--;
char ch = rotationQueue.peek();
rotationQueue.remove();
rotationQueue.add(ch);
if (rotationQueue.equals(originQueue)) {
return true;
}
}在恆定時間內將隊列的頂部元素移動到底部為我們提供了一個新的移位物件來與原點進行比較。
我們看一下演算法複雜度：
- 時間複雜度：最壞情況是 O(n*n)，我們在與原點比較的同時遍歷整個佇列
- 空間複雜度：O(n)
6.3.單元測試
讓我們測試一下，當將旋轉從頂部移動到尾部時，使用佇列是否與原點相符：
@Test
void givenOriginAndRotationInput_whenCheckingUsingQueues_thenIsRotation() {
assertTrue(isRotationUsingQueue("abcd", "cdab"));
assertTrue(isRotationUsingQueue("abcd", "abcd"));
}讓我們測試一下當隊列不相等時：
@Test
void givenOriginAndRotationInput_whenCheckingUsingQueues_thenNoRotation() {
assertFalse(isRotationUsingQueue("abcd", "bbbb"));
assertFalse(isRotationUsingQueue("abcd", "abcde"));
}七、結論
在本文中，我們看到了一些檢查一個字串是否是另一個字串的旋轉的演算法。我們了解如何使用雙源字串和contains()字串方法來搜尋常見字元並斷言相等。類似地，我們可以使用演算法來檢查字串的其餘部分是否在移位位置或使用後綴和前綴匹配。最後，我們還看到了一個使用佇列並將窺視移動到旋轉尾部直到它等於原點的範例。
與往常一樣，本文中提供的程式碼可用 在 GitHub 上。與往常一樣，本文中提供的程式碼可用 在 GitHub 上。