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 − 用最大值初始化 ‘output’ 变量。

步骤2 − 开始遍历数组。

步骤3 − 用零初始化 ‘curr_operations’ 变量，以存储使所有字符串等于第 p 个索引处的字符串所需的总旋转次数。

步骤4 − 使用嵌套循环再次遍历数组。在循环中，通过将数组[p]和数组[q]字符串作为参数传递给 isRotation() 函数来执行，以计算使数组[q]等于数组[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 − 返回 output 的值。

示例

import java.util.*;
public class Main {
    // function to find total number of operations to get alpha string from alpha2
    public static int isRotation(String alpha, String alpha2) {
        // base case
        if (alpha.length() != alpha2.length())
            return -1;
        if (alpha.equals(alpha2))
            return 0;
        Queue<Character> alpha2Queue = new LinkedList<>();
        // push all characters of alpha2 to queue
        for (int i = 0; i < alpha2.length(); i++) {
            alpha2Queue.add(alpha2.charAt(i));
        }
        // Push all characters of alpha to queue
        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; // to store minimum operations
        for (int p = 0; p < len; p++) {
            // to store operations for the current iteration
            int curr_operations = 0;
            // total number of rotations required to make all strings of the array equal to
            // str[i]
            String temp = "";
            for (int q = 0; q < len; q++) {
                int index = isRotation(array[p], array[q]);
                // return -1, if array[q] is not a rotation of array[p]
                if (index == -1)
                    return -1;
                // update curr_operations
                curr_operations += index;
            }
            // get minimum operations
            output = Math.min(curr_operations, output);
        }
        return output;
    }
    // Driver code
    public static void main(String args[]) {
        String array[] = { "abcd", "abcd", "dabc", "bcda" };
        int len = array.length;
        System.out.println(
                "The minimum operations required to make all strings of the array equal is "
                        + minOperations(array, len));
    }
}

输出

The minimum operations required to make all strings of the array equal is 4

时间复杂度 − O(NNK)，其中 O(N*N) 是遍历数组的复杂度，O(K)是遍历字符串的复杂度。

空间复杂度 − O(K)，因为我们使用队列来存储字符串的字符。

方法2

在这个方法中，我们将使用‘+’运算符来合并字符串。然后，我们将使用indexOf()方法在合并的字符串中查找目标字符串的索引。

步骤

步骤1 − 将‘output’变量初始化为最大值，并开始遍历数组。

步骤2 − 将‘curr_operations’初始化为零，并使用另一个嵌套循环遍历数组。

步骤3 − 在临时字符串中，存储数组[q] + 数组[q]的值。

步骤4 − 使用indexOf()方法在‘temp’字符串中找到数组[p]的索引。

步骤5 − 如果索引等于临时字符串的长度，返回−1。

步骤6 − 将索引值添加到‘curr_operations’中。

步骤7 − 将output和curr_operations中的最小值存储到output中。

步骤8 − 返回output。

示例

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++) {
            // to store operations for the current iteration
            int curr_operations = 0;
            // total number of rotations required to make all strings of the array equal to
            // str[i]
            String temp = "";
            for (int q = 0; q < len; q++) {
                // Concatenating string to itself to check whether it is a rotation of arr[i]
                temp = array[q] + array[q];
                // find index of array[p] in temp
                int index = temp.indexOf(array[p]);
                // return -1, if array[q] is not a rotation of array[p]
                if (index == array[p].length())
                    return -1;
                // update curr_operations
                curr_operations += index;
            }
            // get minimum operations
            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(
                "The minimum operations required to make all strings of the array equal is " + minOperations(array, len));
    }
}

输出

The minimum operations required to make all strings of the array equal is 4

时间复杂度 - O(NNK)，因为我们在两个嵌套循环中使用了indexOf()方法。

空间复杂度 - O(1)，因为我们没有使用额外的空间。

第二种方法比第一种方法更优化。而且，第二种方法的代码比第一种方法更易读。程序员还可以使用其他方法来解决相同的旋转字符串问题。