Implementar un trie con la etiqueta insertsearch y startsWith métodos.
Ejemplo:
Trie trie = new Trie();trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Nota:
- Usted puede asumir que todas las entradas se componen de letras minúsculas
a-z. - Se garantiza que todas las entradas no sean cadenas vacías.
Este es un problema de leetcode:
Solución:
Antes de sumergirnos en la solución de este problema, primero entenderemos qué es la estructura de datos Trie en resumen.
Un Trie es una estructura de árbol ordenada que se utiliza principalmente para almacenar cadenas. La razón por la que se utiliza para almacenar cadenas es que tiene un tiempo de recuperación rápido. La complejidad de encontrar una cadena en un Trie es O (m), donde m es la longitud de la cadena. Si hemos almacenado un millón de cadenas en Trie y necesitamos encontrar una cadena en particular, digamos cat, entonces su complejidad será O (3), ¿no es increíble?
El término trie proviene de la recuperación de palabras, ya que hace que la recuperación de una cadena de la colección de cadenas sea muy fácil. Trie también se llama Árbol de Prefijos.
En Trie la raíz está vacía y cada nodo secundario contiene solo un carácter. Por lo tanto, el número de nodos secundarios que puede tener un nodo en particular depende del número de alfabetos en un idioma dado. Supongamos que estamos usando nuestro trie para almacenar palabras en inglés, entonces cada nodo tendrá 26 nodos hijos.
En la imagen anterior hemos mostrado sólo 5 nodos secundarios, pero en la raíz real tendrá 26 de nodos secundarios, uno para cada alfabeto.
Ahora, veamos si necesitamos representar algunas cadenas en la estructura de datos trie, entonces cómo se verá. Supongamos que tenemos que representar pelota, calvo, coche, gato y perro en trie. Esto se verá como se muestra a continuación. En la imagen de abajo, los nodos naranjas significan fin de palabra.
Esta fue la introducción a lo que Trie es, pero la parte principal es cómo Trie puede ser implementado. A continuación veremos cómo se puede implementar Trie.
Cada nodo en Trie debe contener dos piezas de información.
- Una bandera booleana que indica que este nodo es el final de una palabra.
- Una matriz de tamaño 26 (depende del idioma utilizado. 26 es para inglés). Cada índice de esta matriz apunta a otro nodo.
Digamos que cada nodo en Trie está representado por la clase TrieNode. La clase TrieNode tendrá dos campos:
- iSend: Campo booleano.
- hijo: Una matriz de tipo TrieNode.
Entonces, tendremos una clase Trie que contendrá insert, search y startsWith method.
Veamos cómo funcionará insertar paso a paso. Tenemos que insertar gato en nuestro trie.
- Inicialmente solo tenemos nodo raíz. Todos los índices en su matriz contienen null y la bandera iSend también es falsa.
2. Elegimos el primer carácter de cat, es decir, ahora el índice en la matriz será 2. Si no está al tanto, entonces encontramos el índice de cualquier alfabeto en una matriz haciendo char – ‘a’. Al hacer esto, el índice de a es 0, b es 1, c es 2 y así sucesivamente. Vamos al índice 2 de la matriz y le asignamos un nuevo nodo.
3. Ahora movemos nuestro puntero al segundo nodo. El segundo alfabeto en cat es a. Inicializamos el índice 0 a un nuevo nodo.
4. Movemos el puntero al siguiente nodo. El siguiente alfabeto en cat es t. El índice de t es 19. Inicializamos el índice 19 en un nuevo nodo.
5. Nos movemos al siguiente nodo . Ahora no queda más alfabeto para insertar. Así que marcamos este nodo como fin.
a Continuación está el código de Java para insertar método.
public void insert(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
tempNode.child = new TrieNode();
}
tempNode = tempNode.child;
}
tempNode.isEnd = true;
}
A continuación se muestra la solución Java completa para este programa con método de búsqueda e inicio con.
class Trie {
class TrieNode {
static final int ALPHABET_SIZE = 26;
TrieNode child = new TrieNode; boolean isEnd;
}
TrieNode root;
/**
* Initialize your data structure here.
*/
public Trie() {
root = new TrieNode();
}
/**
* Inserts a word into the trie.
*/
public void insert(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
tempNode.child = new TrieNode();
}
tempNode = tempNode.child;
}
tempNode.isEnd = true;
}
/**
* Returns if the word is in the trie.
*/
public boolean search(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
return false;
}
tempNode = tempNode.child;
}
if (tempNode != null && tempNode.isEnd == false) {
return false;
}
return true;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
return false;
}
tempNode = tempNode.child;
}
return true;
}
}