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 − 从第1个索引开始遍历’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()方法将字符串分成两部分，并使用‘+’运算符来合并字符串。