Implémenter un trie avec des méthodes insertsearch et startsWith.
Exemple:
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
Remarque:
- Vous pouvez supposer que toutes les entrées sont composées de lettres minuscules
a-z. - Toutes les entrées sont garanties comme des chaînes non vides.
Ceci est un problème de leetcode:
Solution:
Avant de nous plonger dans la résolution de ce problème, nous comprendrons d’abord ce qu’est la structure de données Trie en bref.
Un Trie est une structure arborescente ordonnée qui est principalement utilisée pour stocker une chaîne. La raison pour laquelle il est utilisé pour stocker une chaîne est qu’il a un temps de récupération rapide. La complexité de trouver une chaîne dans un Trie est O(m), où m est la longueur de la chaîne. Si nous avons stocké un million de chaînes dans Trie et que nous devons trouver une chaîne particulière, disons cat alors sa complexité sera O(3), n’est-ce pas incroyable.
Le terme trie vient du mot récupération car il rend la récupération d’une chaîne de la collection de chaînes très facile. Trie est également appelé arbre de préfixe.
Dans Trie, la racine est vide et chaque nœud enfant ne contient qu’un seul caractère. Ainsi, le nombre de nœuds enfants qu’un nœud particulier peut avoir dépend du nombre d’alphabets dans une langue donnée. Supposons que nous utilisions notre trie pour stocker des mots anglais, alors chaque nœud aura 26 nœuds enfants.
Dans l’image ci-dessus, nous n’avons montré que 5 nœuds enfants, mais la racine réelle aura 26 nœuds enfants, un pour chaque alphabet.
Maintenant, voyons si nous devons représenter quelques chaînes dans la structure de données trie, puis à quoi cela ressemblera. Supposons que nous devions représenter balle, chauve, voiture, chat et chien en trie. Cela ressemblera comme indiqué ci-dessous. Dans l’image ci-dessous, les nœuds orange signifient fin de mot.
C’était une introduction à ce qu’est Trie, mais la partie principale est de savoir comment Trie peut être implémenté. Nous verrons comment Trie peut être mis en œuvre ci-dessous.
Chaque nœud de Trie doit contenir deux informations.
- Un drapeau booléen qui indique que ce nœud est la fin d’un mot.
- Un tableau de taille 26 (dépend de la langue utilisée. 26 est pour l’anglais). Chaque index de ce tableau pointe vers un autre nœud.
Disons que chaque nœud de Trie est représenté par la classe TrieNode. La classe TrieNode aura deux champs :
- isEnd: Champ booléen.
- enfant : Un tableau de type TrieNode.
Ensuite, nous aurons une classe Trie qui contiendra la méthode insert, search et startsWith.
Voyons comment insert fonctionnera étape par étape. Nous devons insérer cat dans notre trie.
- Au départ, nous n’avons que le nœud racine. Tous les index de son tableau contiennent null et l’indicateur isEnd est également false.
2. Nous choisissons le premier caractère du chat, c’est-à-dire Maintenant l’index dans le tableau sera 2. Si vous n’êtes pas au courant, nous trouvons l’index de n’importe quel alphabet dans un tableau en faisant char-’a’. Ce faisant, l’indice de a est 0, b est 1, c est 2 et ainsi de suite. Nous allons à l’index 2 du tableau et lui attribuons un nouveau nœud.
3. Maintenant, nous déplaçons notre pointeur vers le deuxième nœud. Le deuxième alphabet dans cat est a. Nous initialisons donc l’index 0 sur le nouveau nœud.
4. Nous déplaçons le pointeur vers le nœud suivant. L’alphabet suivant dans cat est t. L’indice de t est 19. Nous initialisons l’index 19 au nouveau nœud.
5. Nous passons au nœud suivant. Maintenant, il ne reste plus d’alphabet à insérer. Nous marquons donc ce nœud comme fin.
Voici le code Java de la méthode insert.
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;
}
Voici la solution Java complète pour ce programme avec la méthode search et 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;
}
}