Java 程序实现最小化移动到末尾操作以使所有字符串相等
在这个问题中，我们给出了 n 个字符串，需要通过旋转它们使所有字符串相等。
为了解决这个问题，我们需要从数组中选取任意字符串，并通过旋转它们使所有字符串相等。此外，我们需要计算旋转所有字符串所需的操作总数。我们可以逐个选取每个字符串，使所有其他字符串相等，计算每个字符串的总操作数，然后取其中最小的。
问题描述− 我们给出了一个包含 n 个字符串的数组。所有字符串都是彼此的排列。我们需要计算通过对字符串进行左旋转使所有字符串相等所需的最小操作总数。
示例
输入
array[] = { "abcd", "abcd", "dabc", "bcda" }
输出
4
解释 − 我们可以让所有字符串等于 'abcd'。因此，我们需要 1 次运算将 'dabc' 转换为 'abcd'，并需要 3 次运算将 'bcda' 转换为 'abcd'。
输入
array = {'pq', 'pq', 'pq'}
输出
0
解释 − 所有字符串都相等。因此，我们不需要执行任何运算。
输入
array = {‘ab’, ‘bd’, ‘cd’}
输出
-1
解释 − 给定的字符串不是彼此的排列。因此，打印 -1。
方法 1
在此方法中，我们将遍历字符串数组。我们将选择一个字符串，并通过旋转使所有字符串都等于该字符串。此外，我们还会计算每个字符串的操作次数，并取最小操作次数。
这里，我们使用队列数据结构来计算使两个字符串相等所需的最小旋转次数。
算法
步骤 1 - 使用最大值初始化"输出"。
步骤 2 - 开始遍历数组。
步骤 3 - 使用零初始化"curr_operations"变量，以存储使所有字符串等于第 p 个索引处的字符串所需的总旋转次数。
步骤 4 - 使用嵌套循环再次遍历数组。在循环中，通过将 array[p] 和 array[q] 字符串作为参数传递来执行 isRotation() 函数，以计算使 array[q] 等于 array[p] 所需的旋转次数。
步骤 4.1 − 在 isRotation() 函数中，如果两个字符串的长度不相等，则返回 -1。
步骤 4.2 − 如果两个字符串相等，则返回 0。
步骤 4.3 − 创建一个"alpha2Queue"队列，并将 alpha2 字符串的所有字符存储在其中。
步骤 4.4 − 创建一个"alpha1Queue"队列，并将 alpha 字符串的所有字符存储在其中。
步骤 4.5 − 将"k"初始化为 0，以存储旋转次数。使用 while 循环进行迭代。
步骤 4.6− 在每次迭代中，从"alpha1Queue"队列中移除字符并将其压入队列末尾。之后，匹配两个队列。如果两个队列相等，则返回 K 的值。
步骤 4.7 − 在函数末尾返回 -1。
步骤 5 − 如果 isRotation() 函数的返回值为 -1，则返回 -1。否则，将索引值添加到"curr_operations"变量中。
步骤 7 − 使用 Math.min() 方法从 output 和 curr_operations 中获取最小值，并将其存储在 output 变量中。
步骤 8 − 返回输出值。
示例
import java.util.*;
public class Main {
// 函数用于计算从 alpha2 获取 alpha 字符串所需的操作总数
public static int isRotation(String alpha, String alpha2) {
// 基本情况
if (alpha.length() != alpha2.length())
return -1;
if (alpha.equals(alpha2))
return 0;
Queue<Character> alpha2Queue = new LinkedList<>();
// 将 alpha2 的所有字符推送到队列
for (int i = 0; i < alpha2.length(); i++) {
alpha2Queue.add(alpha2.charAt(i));
}
// 将 alpha 的所有字符推送到队列
Queue<Character> alpha1Queue = new LinkedList<>();
for (int i = 0; i < alpha.length(); i++) {
alpha1Queue.add(alpha.charAt(i));
}
int k = 0;
while (k < alpha.length()) {
k++;
char ch = alpha1Queue.peek();
alpha1Queue.remove(); // deque
alpha1Queue.add(ch); // enque
// queue matching
if (alpha1Queue.equals(alpha2Queue))
return k;
}
return -1;
}
static int minOperations(String array[], int len) {
int output = Integer.MAX_VALUE; // 存储最小操作数
for (int p = 0; p < len; p++) {
// 存储当前迭代的操作数
int curr_operations = 0;
// 使数组中所有字符串相等所需的旋转总数
// str[i]
String temp = "";
for (int q = 0; q < len; q++) {
int index = isRotation(array[p], array[q]);
// 如果 array[q] 不是 array[p] 的旋转，则返回 -1
if (index == -1)
return -1;
// 更新 curr_operations
curr_operations += index;
}
// 获取最小操作数
output = Math.min(curr_operations, output);
}
return output;
}
// 驱动代码
public static void main(String args[]) {
String array[] = { "abcd", "abcd", "dabc", "bcda" };
int len = array.length;
System.out.println(
"使数组所有字符串相等所需的最少操作是 "
+ minOperations(array, len));
}
}
输出
使数组所有字符串相等所需的最少操作是 4
时间复杂度− O(N*N*K)，其中 O(N*N) 表示遍历数组，O(K) 表示遍历字符串。
空间复杂度− O(K)，因为我们使用队列存储字符串字符。
方法 2
在此方法中，我们将使用"+"运算符合并字符串。之后，我们将使用 indeOf() 方法在合并后的字符串中找到目标字符串的索引。
算法
步骤 1 - 使用最大值初始化"output"变量，并开始遍历数组。
步骤 2 - 使用零初始化"curr_operations"，并使用另一个嵌套循环遍历数组。
步骤 3 - 在临时字符串中，存储 array[q] + array[q] 的值。
步骤 4 - 使用 indexOf() 方法在"temp"字符串中找到 array[p] 的索引。
步骤 5 - 如果索引等于临时字符串的长度，则返回 -1。
步骤 6 - 添加索引值到'curr_operations'。
步骤 7 - 将输出和 curr_operations 中的最小值存储到输出中。
步骤 8 - 返回输出。
示例
import java.util.*;
public class Main {
static int minOperations(String array[], int len) {
// to store minimum operations
int output = Integer.MAX_VALUE;
for (int p = 0; p < len; p++) {
// 存储当前迭代的操作
int curr_operations = 0;
// 使数组中所有字符串相等所需的旋转次数
// str[i]
String temp = "";
for (int q = 0; q < len; q++) {
// 将字符串连接到自身，检查它是否是 arr[i] 的旋转
temp = array[q] + array[q];
// 在 temp 中找到 array[p] 的索引
int index = temp.indexOf(array[p]);
// 如果 array[q] 不是 array[p] 的旋转，则返回 -1
if (index == array[p].length())
return -1;
// 更新 curr_operations
curr_operations += index;
}
// 获取最小操作数
output = Math.min(curr_operations, output);
}
return output;
}
public static void main(String args[]) {
String array[] = { "abcd", "abcd", "dabc", "bcda" };
int len = array.length;
System.out.println(
"使数组所有字符串相等所需的最少操作是 " + minOperations(array, len));
}
}
输出
使数组所有字符串相等所需的最少操作是 4
时间复杂度− O(N*N*K)，因为我们在两个嵌套循环中使用了 indexOf() 方法。
空间复杂度− O(1)，因为我们没有使用额外的空间。
第二种方法比第一种方法更加节省空间。此外，第二种方法的代码比第一种方法更具可读性。程序员也可以使用其他方法，使旋转字符串相同来解决这个问题。
