[Leetcode] 0269. Diccionario alienígena

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Duro

Hay un nuevo idioma alienígena que utiliza el alfabeto inglés. Sin embargo, desconoces el orden de las letras.

Se le proporciona una lista de cadenas. palabras del diccionario del idioma alienígena. Ahora se afirma que las cadenas en palabras son ordenado lexicográficamente por las reglas de este nuevo lenguaje.

Si esta afirmación es incorrecta y la disposición dada de la cuerda en palabras no puede corresponder a ningún orden de letras, devolver "".

De lo contrario, regrese una cadena de letras únicas en el nuevo idioma alienígena ordenadas en orden lexicográficamente creciente por las reglas del nuevo idioma. Si hay varias soluciones, regrese cualquiera de ellos.

Ejemplo 1:

Aporte: palabras = ["wrt","wrf","er","ett","rftt"]
Producción: "wertf"

Ejemplo 2:

Aporte: palabras = ["z","x"]
Producción: "zx"

Ejemplo 3:

Aporte: palabras = ["z","x","z"]
Producción: ""
Explicación: El pedido no es válido, así que devuélvelo. "".

Restricciones:

1 <= palabras.longitud <= 100
1 <= palabras[i].longitud <= 100
palabras[yo] consta únicamente de letras minúsculas en inglés.

Pitón

				
					Complejidad de tiempo de #: O(C) Complejidad de espacio de #: O(1) al escribir import List clase Solución: def alienOrder(self, palabras: Lista[str]) -> str: reverseAdjList = {c: [] para palabra en palabras para c en palabra} para primera palabra, segunda palabra en zip(palabras, palabras[1:]): para c, d en zip(primera palabra, segunda palabra): si c != d: ReverseAdjList[d].append(c) break else : si len(segundaPalabra) < len(primeraPalabra): return "" visto = {} salida = [] def visita(nodo): si el nodo está visto: regresa visto[nodo] visto[nodo] = False para el siguienteNodo en inversaAdjList[ nodo]: resultado = visita(siguienteNodo) si no resultado: retorno Falso visto[nodo] = Verdadero salida.append(nodo) retorno Verdadero si no todos(visita(nodo) para nodo en inversaAdjList): retorno "" retorno "". unir(salida) palabras = ["wrt", "wrf", "er", "ett", "rftt"] imprimir(Solución().alienOrder(palabras))

Duro

Pitón

Artículos relacionados