[Leetcode] 1804. Implementar Trie II

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.
• int countWordsEqualTo(Cadena palabra) Devuelve el número de instancias de la cadena. palabra en el trie.
• int countWordsStartingWith(Cadena prefijo) Devuelve el número de cadenas en el trie que tienen la cadena prefijo como prefijo.
• void borrar(Cadena palabra) Borra la cadena palabra del trie.

Ejemplo 1:

Aporte
["Trie", "insertar", "insertar", "contarPalabrasIgualesA", "contarPalabrasQueEmpiezanCon", "borrar", "contarPalabrasIgualesA", "contarPalabrasQueEmpiezanCon", "borrar", "contarPalabrasQueEmpiezanCon"] [[], ["manzana"], ["manzana"], ["manzana"], ["manzana"], ["manzana"], ["manzana"], ["aplicación"]]
Producción
[nulo, nulo, nulo, 2, 2, nulo, 1, 1, nulo, 0]

Explicación
Trie trie = nuevo Trie(); trie.insert("manzana"); // Inserta "manzana". trie.insert("manzana"); // Inserta otra "manzana". trie.countWordsEqualTo("manzana"); // Hay dos instancias de "apple", por lo que se devuelve 2. trie.countWordsStartingWith("app"); // "app" es un prefijo de "apple", por lo que devuelve 2. trie.erase("apple"); // Borra una "manzana". trie.countWordsEqualTo("manzana"); // Ahora solo hay una instancia de "apple", por lo que se devuelve 1. trie.countWordsStartingWith("app"); // devuelve 1 trie.erase("manzana"); // Borra "manzana". Ahora el trie está vacío. trie.countWordsStartingWith("aplicación"); // devolver 0

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 4 llamadas en total se hará a insertar, contarPalabrasIgualesA, contarPalabrasQueEmpiezanCon, y borrar.
• Se garantiza que para cualquier llamada de función a borrar, la cuerda palabra existirá en el trie.