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

 Add passwordless user experiences to your app

HackerNoon Mobile

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

Demasiado Largo; Para Leer

Companies Mentioned

@rakhmedovrs

HISTORIAS RELACIONADAS