用 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("恢复原始字符串所需的旋转次数为: ");
System.out.println(totalRotations(str));
}
}
输出
恢复原始字符串所需的旋转次数为: 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("恢复原始字符串所需的旋转次数总计为: ");
System.out.println(totalRotations(str));
}
}
输出
恢复原始字符串所需的旋转次数总计为: 5
时间复杂度− O(N^2)，因为我们将字符串分成两部分。
空间复杂度− O(N)，用于存储合并后的子字符串。
我们学习了两种解决这个问题的方法。此外，我们还使用了 substr() 方法将字符串分成两部分，并使用"+"运算符合并字符串。
