Dadas n strings que son permutaciones entre sí. Necesitamos hacer que todas las strings sean iguales con una operación que tome el carácter frontal de cualquier string y lo mueva al final.
Ejemplos:
Input : n = 2
arr[] = {"molzv", "lzvmo"}
Output : 2
Explanation: In first string, we remove
first element("m") from first string and
append it end. Then we move second character
of first string and move it to end. So after
2 operations, both strings become same.
Input : n = 3
arr[] = {"kc", "kc", "kc"}
Output : 0
Explanation: already all strings are equal.
El movimiento para finalizar la operación es básicamente una rotación a la izquierda. Usamos el enfoque discutido en verificar si las strings son rotaciones entre sí o no para contar el número de operaciones de movimiento al frente requeridas para hacer que dos strings sean iguales. Consideramos una por una cada string como la string de destino. Contamos las rotaciones requeridas para hacer que todas las demás strings sean iguales al objetivo actual y finalmente devolvemos el mínimo de todos los conteos.
A continuación se muestra la implementación del enfoque anterior.
Java
// Java program to make all
// strings same using move
// to end operations.
import java.util.*;
class GFG
{
// Returns minimum number of
// moves to end operations
// to make all strings same.
static int minimunMoves(String arr[], int n)
{
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
{
int curr_count = 0;
// Consider s[i] as target
// string and count rotations
// required to make all other
// strings same as str[i].
String tmp = "";
for (int j = 0; j < n; j++)
{
tmp = arr[j] + arr[j];
// find function returns the
// index where we found arr[i]
// which is actually count of
// move-to-front operations.
int index = tmp.indexOf(arr[i]);
// If any two strings are not
// rotations of each other,
// we can't make them same.
if (index == arr[i].length())
return -1;
curr_count += index;
}
ans = Math.min(curr_count, ans);
}
return ans;
}
// Driver code
public static void main(String args[])
{
String arr[] = {"xzzwo", "zwoxz",
"zzwox", "xzzwo"};
int n = arr.length;
System.out.println(minimunMoves(arr, n));
}
}
// This code is contributed
// by Kirti_Mangal
Producción:
5
Complejidad de tiempo: O(N 3 ) (N 2 debido a que se usaron dos bucles anidados y N es para la función indexOf() que usó el bucle for interno)
¡ Consulte el artículo completo sobre las operaciones de movimiento mínimo para finalizar para hacer que todas las strings sean iguales para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA