Cómo implementar Trie (Árbol de prefijos) - Preguntas ciegas de 75 LeetCode

Descripción de la tarea:

Un trie (pronunciado como "try") o árbol de prefijos es una estructura de datos de árbol utilizada para almacenar y recuperar claves de manera eficiente en un conjunto de datos de cadenas. Hay varias aplicaciones de esta estructura de datos, como autocompletar y corrector ortográfico.

Implementar la clase Trie:

• Trie() Inicializa el objeto trie.
• void insert(String word) Inserta la cadena de word en el trie.
• boolean search(String word) Devuelve true si la word de la cadena está en el trie (es decir, se insertó antes), y false en caso contrario.
• boolean startsWith(String prefix) Devuelve true si hay una word de cadena insertada previamente que tiene el prefijo prefix y false de lo contrario.

Ejemplo 1:

 Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true]

 Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

Restricciones:

• 1 <= word.length, prefix.length <= 2000
• word y el prefix consisten solo en letras minúsculas en inglés.
• Se realizarán un máximo 3 * 10^4 llamadas en total para insert , search y startsWith .

Razonamiento:

Trie es la estructura de datos clásica que se usa ampliamente. Uno de los usos más famosos es la búsqueda de texto. Tomemos Google.com como ejemplo.

el ejemplo de google

¿Alguna vez ha notado que cada vez que comienza a escribir una frase de búsqueda en una barra de búsqueda, casi de inmediato recibe alguna sugerencia del sistema de búsqueda? Apuesto a que la respuesta es "Sí". La estructura de datos de Trie lo hace posible.

Agreguemos algunas palabras a Trie y veamos cómo se ve así:

Ejemplo de Trie con algunas palabras

El Trie anterior contiene palabras: Algorithm, Animation, Ant, Apache, Append, Apple, Application, Apricot. Como puede notar, tratamos cada palabra como una secuencia de caracteres.

Comenzando desde el primer carácter de cada palabra, lo adjuntamos a la raíz del Trie y bajamos hasta llegar al último carácter de cada palabra.

Una vez que llegamos al final de una palabra, marcamos ese último Nodo como el final de la palabra. Espero que ahora te quede claro cómo funciona en general. Si todavía tiene problemas con eso, le recomiendo que lea el artículo de Wikipedia .

Solución:

Vamos a implementar Trie con el siguiente método:

https://gist.github.com/RakhmedovRS/a53ea510ad97088fdfd4829209d405b2

Como vimos en el ejemplo de Trie real, tuvimos que notar que, como cualquier otra estructura de datos de Tree , consta de piezas más pequeñas que generalmente se denominan Node . Vamos a introducir esta pequeña parte:

https://gist.github.com/RakhmedovRS/bb2a188cd156565b692af1f5262d96a3

Algunas cosas que necesitamos ver más de cerca aquí:

Tenemos la matriz booleana chars que nos dirá si tenemos caracteres particulares en un nodo particular. isEnd variable booleana que responde solo una pregunta, ya sea que el nodo actual sea o no el final de una palabra en nuestro Trie. Por último, pero no menos importante, la matriz TrieNode infantil almacena los TrieNodes secundarios del TrieNode actual.

Veamos otros métodos, uno por uno:

El método void insert(String word) no devuelve nada y acepta word para insertar en el Trie:

https://gist.github.com/RakhmedovRS/b460db4fd040a47ca33e8afc401af7c0

Comenzando desde la raíz del Trie, iteramos a través de cada carácter en la palabra proporcionada y creamos un nuevo TrieNode cada vez si no tenemos uno. En el último carácter de Word, marcamos TrieNode como isEnd.

El siguiente método en nuestra lista es boolean search(String word) que busca una palabra en particular en Trie y devuelve un valor booleano dependiendo de si Trie la contiene o no. Como entrada, toma una palabra.

https://gist.github.com/RakhmedovRS/18bb68c4e83f3c602afa4a338e96fbc2

Aquí hacemos lo mismo que en el método anterior excepto por algunas cosas. Iterar a través de cada carácter en la palabra proporcionada y si no tenemos un hijo con el siguiente carácter, devolvemos falso. Al final de una palabra, devolvemos el valor del nodo actual de isEnd .

Por último, el método boolean startsWith(String prefix) toma el prefijo y devuelve verdadero si tenemos un prefijo en nuestro Trie; de lo contrario, devolvemos falso.

https://gist.github.com/RakhmedovRS/d25842ef37c339e6260ef50097713e84

Este método hace completamente lo mismo que el anterior excepto por una sola cosa. Si logramos iterar a través de todo el prefijo, devolvemos verdadero, porque estamos buscando el prefijo y no una palabra completa; de lo contrario, devolvemos falso.

Como siempre al final del artículo, demuestro el código fuente completo del problema

https://gist.github.com/RakhmedovRS/cff7b0ea83d0a598c86c7b9aac834425

Tiene una complejidad lineal de tiempo y espacio y tiene la siguiente posición entre las soluciones de otras personas.

También publicado aquí .