[Leetcode] 0208. Implementar Trie

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 ⁴ 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"))

Pitón

Artículos relacionados