獲取相同字串所需最小旋轉次數的 Java 程式

---

在本教程中，我們需要編寫一個 Java 程式來計算獲取原始字串所需的最小旋轉總數。

我們可以透過獲取原始字串的旋轉子串或將原始字串自身連線起來來解決這個問題。

問題陳述 - 我們給定長度為 N 的字串 str。任務是找到我們需要執行的最小旋轉總數才能獲得原始字串。

示例

輸入

str = "bcdbcd";

輸出

3

解釋 - 我們需要進行 3 次旋轉才能獲得原始字串。

• 第一次旋轉後，字串將是“cdbcdb”。

• 第二次旋轉後，字串將是“dbcdbc”。

• 第三次旋轉後，字串將是“bcdbcd”。

輸入

 str = ‘efg’

輸出

3

解釋 - 我們需要進行總共 3 次左旋轉才能獲得原始字串。

方法 1

在這種方法中，我們將使用 substring() 方法從原始字串中獲取特定長度的子字串。之後，我們將連線字串的左右部分，並使用字串索引計算旋轉總數。

演算法

步驟 1 - 在 temp_str 變數中，儲存“alpha + alpha”。

步驟 2 - 定義“str_len”變數並存儲字串的長度。

步驟 3 - 從第一個索引遍歷“temp_str”字串到字串的長度。

步驟 4 - 獲取從第 p 個索引開始，長度等於“str_len”的子字串。

步驟 5 - 使用 equals() 方法檢查 alpha 是否等於“substr”。

步驟 6 - 如果是，則返回 p。

步驟 7 - 最後，返回“str_len”。

示例

import java.util.*;

public class Main {
    static int totalRotations(String alpha) {
        // Merge the string
        String temp_Str = alpha + alpha;
        int str_len = alpha.length();
        // traverse the string
        for (int p = 1; p <= str_len; p++) {
            // getting rotational substring
            String subStr = temp_Str.substring(p, p + alpha.length());
            // return p if str and subStr are equal
            if (alpha.equals(subStr))
                return p;
        }
        return str_len;
    }
    public static void main(String[] args) {
        String str = "bcdbcd";
        System.out.println("The total number of rotations required to get original string again are: ");
        System.out.println(totalRotations(str));
    }
}

輸出

The total number of rotations required to get original string again are: 
3

時間複雜度 - O(N^2)，因為我們在迴圈內查詢子字串。

空間複雜度 - O(N)，用於儲存連線的字串。

方法 2

在這種方法中，我們將原始字串分成兩部分。之後，我們將合併字串的左右部分。如果最終字串等於原始字串，我們可以說總旋轉次數等於我們將字串分成兩部分的索引。

演算法

步驟 1 - 將“operations”初始化為零。

步驟 2 - 遍歷字串。

步驟 3 - 獲取從第 p 個索引開始的子字串。

步驟 4 - 獲取從第 0 個索引開始，長度為 p 的子字串。

步驟 5 - 如果 alpha 和 substr 相同，則更新“operations”的值。

步驟 6 - 如果“operations”等於 0，則返回 0。否則，返回“operations”變數的值。

示例

import java.util.*;

public class Main {
    static int totalRotations(String alpha) {
        int operations = 0; // to store total rotations
        int len = alpha.length();
        // traverse the string
        for (int p = 1; p < alpha.length(); p++) {
            String subStr = alpha.substring(p) + alpha.substring(0, p);
            // If substring [p, len-1] + [0, p-1] == alpha, then break
            if (alpha.equals(subStr)) {
                operations = p;
                break;
            }
        }
        if (operations == 0)
            return len;
        return operations;
    }
    public static void main(String[] args) {
        String str = "bcdbc";
        System.out.println("The total number of rotations required to get the original string again are: ");
        System.out.println(totalRotations(str));
    }
}

輸出

The total number of rotations required to get the original string again are: 
5

時間複雜度 - O(N^2)，因為我們將字串分成兩部分。

空間複雜度 - O(N)，用於儲存組合的子字串。

我們學習了兩種解決問題的方法。此外，我們還使用了 substr() 方法將字串分成兩部分，並使用“+”運算符合並字串。