[Leetcode] 0208. Implementar Trie

/ Leetcode, artículo técnico / Por

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

A intentar (pronunciado como “try”) o árbol de prefijos es una estructura de datos de árbol que se utiliza para almacenar y recuperar claves de manera eficiente en un conjunto de datos de cadenas. Hay varias aplicaciones de esta estructura de datos, como el autocompletado y el corrector ortográfico.

Implementar la clase Trie:

  • Intenta() Inicializa el objeto trie.
  • void insert(Cadena palabra) Inserta la cadena palabra en el trie.
  • búsqueda booleana (cadena palabra) Devoluciones verdadero Si la cadena palabra está en el trie (es decir, se insertó antes), y FALSO de lo contrario.
  • booleano startsWith(prefijo de cadena) Devoluciones verdadero si hay una cadena insertada previamente palabra que tiene el prefijo prefijo, y FALSO de lo contrario.

 

Ejemplo 1:

Aporte
["Trie", "insertar", "buscar", "buscar", "inicia con", "insertar", "buscar"] [[], ["manzana"], ["manzana"], ["aplicación"], ["aplicación"], ["aplicación"]]
Producción
[nulo, nulo, verdadero, falso, verdadero, nulo, verdadero]

Explicación
Trie trie = nuevo Trie(); trie.insert("manzana"); trie.search("manzana"); // devuelve Verdadero trie.search("app"); // devuelve Falso trie.startsWith("app"); // devuelve Verdadero trie.insert("app"); trie.search("aplicación"); // devuelve Verdadero

 

Restricciones:

  • 1 <= longitud de palabra, longitud de prefijo <= 2000
  • palabra y prefijo consisten únicamente en letras minúsculas del alfabeto inglés.
  • A lo sumo 3 * 10 4 llamadas en total se hará a insertar, buscar, y comienza con.

Tabla de contenido

Pitón

				
					# insert() # complejidad de tiempo: O(l) # complejidad de espacio: O(l) # search() # complejidad de tiempo: O(l) # complejidad de espacio: O(1) # search prefix() # complejidad de tiempo: O(l) # complejidad de espacio: O(1) clase TrieNode: def __init__(self, char: str = ""): self.char = char self.children = {} self.isEnd = False clase Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str): nodo = self.root para c en palabra: si c en nodo.children: nodo = nodo.children[c] sino: nuevoNodo = TrieNode() nodo.children[c] = nuevoNodo nodo = nuevoNodo nodo.isEnd = True def búsqueda(self, palabra: str): nodo = self.root para c en palabra: si c no está en nodo.children: devuelve Falso nodo = nodo.children[c] devuelve nodo.isEnd def startsWith(self, prefijo: str): nodo = self.root para c en prefijo: si c no está en nodo.children: devuelve Falso nodo = nodo.children[c] devuelve Verdadero # Su objeto Trie se instanciará y se llamará como tal: trie = Trie() trie.insert("apple") print(trie.search("apple")) print(trie.search("app")) print(trie.startsWith("app")) trie.insert("app") print(trie.search("app"))

Artículos relacionados