获取相同字符串所需最小旋转次数的 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() 方法将字符串分成两部分，并使用“+”运算符合并字符串。