Implementar uma trie com insertsearch e startsWith métodos.
Exemplo:
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:
- Você pode assumir que todas as entradas são consistir de letras minúsculas
a-z. - todas as entradas são garantidas como cadeias de caracteres não-vazias.
Este é um problema de código LEET:
solução:
Antes de mergulharmos na solução deste problema, vamos primeiro entender o que a estrutura de dados Trie é em breve.
uma Trie é uma estrutura de árvore ordenada que é usada principalmente para armazenar strings. A razão pela qual ele é usado para armazenar String é que ele tem tempo de recuperação rápido. A complexidade de encontrar uma cadeia em uma Trie é O (m), onde m é o comprimento da cadeia. Se nós temos armazenado um milhão de cordas em Trie e nós precisamos encontrar uma corda particular, vamos dizer cat então sua complexidade será O (3), não é incrível?
O termo trie veio da recuperação da palavra, uma vez que torna a recuperação de uma string da coleção de strings muito fácil. Trie também é chamado de árvore prefixo.
In Trie the root is empty and each child node contains only one character. Assim, o número de nós-filhos, um nó particular pode ter depende do número de alfabetos em uma determinada língua. Suponha que estamos usando nossa trie para armazenar palavras em inglês, então cada nó terá 26 nós-filhos.
Na imagem acima temos mostrado apenas 5 nós da criança mas, na real, raiz terá 26 de criança nós, um para cada alfabeto.
Agora, vamos ver se precisamos representar algumas strings na estrutura de dados trie então como ele vai parecer. Suponha que temos de representar bola, careca, carro, gato e cão em trie. Isto irá olhar como mostrado abaixo. Na imagem abaixo, os nós laranja significam fim de palavra.
Esta foi a introdução para o que Trie é, mas a parte principal é como Trie pode ser implementado. Examinaremos a forma como a Trie pode ser implementada a seguir.cada nó em Trie deve conter duas informações.
- uma bandeira booleana que diz que este nó é o fim de uma palavra.
- uma matriz de tamanho 26 (depende da linguagem utilizada. 26 é para Inglês). Cada índice neste array aponta para outro nó.
digamos que cada nó em Trie é representado pela classe TrieNode. A classe Trienódica terá dois campos:
- isEnd: campo booleano.
- criança: uma matriz do tipo TrieNode.
então, teremos uma classe Trie que conterá insert, search e startsWith método.
Let’s see how insert will work step by step. Temos de inserir gato na nossa trie.
- inicialmente temos apenas nó raiz. Todos os índices em sua matriz contém a bandeira nula e isEnd também é falsa.
2. Nós escolhemos o primeiro personagem de cat I. E. C. Agora o índice na matriz será 2. Se você não está ciente, então nós encontramos o índice de qualquer alfabeto em array fazendo char-‘a’. Ao fazer isso o índice de A é 0, b é 1, c é 2 e assim por diante. Vamos ao index 2 da array e atribuímos – lhe um novo nó.
3. Agora movemos o ponteiro para o segundo nó. O segundo alfabeto em cat é a. Então inicializamos o índice 0 para um novo nó.
4. Movemos o ponteiro para o próximo nó. O próximo alfabeto em cat é T. O índice de t é 19. Inicializamos o índice 19 para um novo nó.
5. Vamos para o próximo nó . Agora não há mais alfabeto para ser inserido. Então marcamos este nó como fim.
Abaixo está o código Java para o método de inserção.
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;
}
abaixo está a solução Java completa para este programa com o método de pesquisa e startsWith.
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;
}
}