Cómo implementar Trie (Árbol de prefijos) - Preguntas ciegas de 75 LeetCode by@rakhmedovrs
98,668 lecturas

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

2022/07/24
4 min
por @rakhmedovrs 98,668 lecturas
tldt arrow
ES
Read on Terminal Reader

Demasiado Largo; Para Leer

Trie 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 autocompletar y corrector ortográfico. La estructura de datos Trie es la estructura de datos clásica que se usa ampliamente en la búsqueda de texto. Necesitamos implementar Trie con el siguiente método: Trie() y Trie.insert(). En el ejemplo real de Trie, tuvimos que introducir una pequeña parte de la estructura de datos que consta de piezas más pequeñas llamadas **Tree. nodos.

Companies Mentioned

Mention Thumbnail
Mention Thumbnail
featured image - Cómo implementar Trie (Árbol de prefijos) - Preguntas ciegas de 75 LeetCode
Ruslan Rakhmedov HackerNoon profile picture

@rakhmedovrs

Ruslan Rakhmedov

Senior Software Engineer. As a hobby I do competitive programming...

Aprender Mas
LEARN MORE ABOUT @RAKHMEDOVRS'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart

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.

image

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í:

image

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:

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:

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:

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.

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.

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

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

Detalle de envío

Detalle de envío


También publicado aquí .

HISTORIAS RELACIONADAS

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa