Dada una array de tamaño n*n, la tarea es encontrar si todas las filas son rotaciones circulares entre sí o no.
Ejemplos:
Entrada: mat[][] = 1, 2, 3
3, 1, 2
2, 3, 1
Salida: Sí, todas las filas se rotan por permutación entre sí.
Entrada: mat[3][3] = 1, 2, 33, 2, 1
1, 3, 2
Salida: No, Explicación: Como 3, 2, 1 no es una permutación rotada o circular de 1, 2, 3
La idea se basa en el siguiente artículo.
Un programa para verificar si las strings son rotaciones entre sí o no.
Pasos :
- Cree una string de elementos de la primera fila y concatene la string consigo misma para que las operaciones de búsqueda de strings se puedan realizar de manera eficiente. Deje que esta string sea str_cat.
- Atraviese todas las filas restantes. Para cada fila que se recorre, cree una string str_curr de los elementos de la fila actual. Si str_curr no es una substring de str_cat, devuelve falso.
- Devolver verdadero.
A continuación se muestra la implementación de los pasos anteriores.
Java
// Java program to check if all rows of a matrix
// are rotations of each other
class GFG
{
static int MAX = 1000;
// Returns true if all rows of mat[0..n-1][0..n-1]
// are rotations of each other.
static boolean isPermutedMatrix(int mat[][], int n)
{
// Creating a string that contains
// elements of first row.
String str_cat = "";
for (int i = 0; i < n; i++)
{
str_cat = str_cat + "-" + String.valueOf(mat[0][i]);
}
// Concatenating the string with itself
// so that substring search operations
// can be performed on this
str_cat = str_cat + str_cat;
// Start traversing remaining rows
for (int i = 1; i < n; i++)
{
// Store the matrix into vector in the form
// of strings
String curr_str = "";
for (int j = 0; j < n; j++)
{
curr_str = curr_str + "-" + String.valueOf(mat[i][j]);
}
// Check if the current string is present in
// the concatenated string or not
if (str_cat.contentEquals(curr_str))
{
return false;
}
}
return true;
}
// Drivers code
public static void main(String[] args)
{
int n = 4;
int mat[][] = {{1, 2, 3, 4},
{4, 1, 2, 3},
{3, 4, 1, 2},
{2, 3, 4, 1}
};
if (isPermutedMatrix(mat, n))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
/* This code contributed by PrinciRaj1992 */
Yes
Complejidad temporal: O(n 3 )
Espacio auxiliar: O(n)
Consulte el artículo completo sobre Comprobar si todas las filas de una array son rotaciones circulares entre sí 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