Descripción de la tarea:  Un   (pronunciado como "try") o   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. trie árbol de prefijos  Implementar la clase Trie:    Inicializa el objeto trie. Trie()    Inserta la cadena de   en el trie. void insert(String word) word    Devuelve   si la   de la cadena está en el trie (es decir, se insertó antes), y   en caso contrario. boolean search(String word) true word false    Devuelve   si hay una   de cadena insertada previamente que tiene el prefijo   y   de lo contrario. boolean startsWith(String prefix) true word prefix false   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    y el   consisten solo en letras minúsculas en inglés. word prefix  Se realizarán un máximo   llamadas   para   ,   y   . 3 * 10^4 en total insert search startsWith  Razonamiento:    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.  Trie  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   y bajamos hasta llegar al último carácter de cada palabra. Trie  Una vez que llegamos al final de una palabra, marcamos ese último   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   . Nodo 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   real, tuvimos que notar que, como cualquier otra estructura de datos de   , consta de piezas más pequeñas que generalmente se denominan   . Vamos a introducir esta pequeña parte: Trie Tree Node   https://gist.github.com/RakhmedovRS/bb2a188cd156565b692af1f5262d96a3  Algunas cosas que necesitamos ver más de cerca aquí:  Tenemos la matriz booleana   que nos dirá si tenemos caracteres particulares en un nodo particular.   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   almacena los TrieNodes secundarios del TrieNode actual. chars isEnd infantil  Veamos otros métodos, uno por uno:  El método   no devuelve nada y acepta word para insertar en el Trie: void insert(String word)   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   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. boolean search(String word)   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   toma el prefijo y devuelve verdadero si tenemos un prefijo en nuestro Trie; de lo contrario, devolvemos falso. boolean startsWith(String prefix)   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í

Apache

Apple

Google

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Make resilience your competitive advantage

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

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

De los foros a los feeds: cómo los algoritmos de las redes sociales influyen en la interacción digital

La fuga rápida del sistema Claude Sonnet 3.5: un análisis forense

Toque para ganar: Telegram puede incorporar a los próximos 10 mil millones de usuarios de criptomonedas antes de Solana

Cómo mejorar su flujo de trabajo 10 veces: 17 aplicaciones esenciales

De los foros a los feeds: cómo los algoritmos de las redes sociales influyen en la interacción digital

La fuga rápida del sistema Claude Sonnet 3.5: un análisis forense

Toque para ganar: Telegram puede incorporar a los próximos 10 mil millones de usuarios de criptomonedas antes de Solana

Cómo mejorar su flujo de trabajo 10 veces: 17 aplicaciones esenciales

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps