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, ya que 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.
Python3
# Python3 program to check if all rows
# of a matrix are rotations of each other
MAX = 1000
# Returns true if all rows of mat[0..n-1][0..n-1]
# are rotations of each other.
def isPermutedMatrix(mat, n) :
# Creating a string that contains
# elements of first row.
str_cat = ""
for i in range(n) :
str_cat = str_cat + "-" + str(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 i in range(1, n) :
# Store the matrix into vector
# in the form of strings
curr_str = ""
for j in range(n) :
curr_str = curr_str + "-" + str(mat[i][j])
# Check if the current string is present
# in the concatenated string or not
if (str_cat.find(curr_str)) :
return True
return False
# Driver code
if __name__ == "__main__" :
n = 4
mat = [[1, 2, 3, 4],
[4, 1, 2, 3],
[3, 4, 1, 2],
[2, 3, 4, 1]]
if (isPermutedMatrix(mat, n)):
print("Yes")
else :
print("No")
# This code is contributed by Ryuga
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