implementați o trie cu insertsearch și startsWith metode.

exemplu:

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

notă:

• puteți presupune că toate intrările sunt formate din litere micia-z.
• toate intrările sunt garantate a fi șiruri non-goale.

aceasta este o problemă leetcode:

soluție:

înainte de a ne arunca cu capul în rezolvarea acestei probleme, vom înțelege mai întâi ce Trie structura de date este pe scurt.

Un Trie este o structură arborescentă ordonată, care este folosit mai ales pentru a stoca șir. Motivul pentru care este folosit pentru a stoca șir este că are timp de recuperare rapidă. Complexitatea găsirii unui șir într-un Trie este O(m), unde m este lungimea șirului. Dacă am stocat un milion de șiruri în Trie și trebuie să găsim un anumit șir, să spunem pisică atunci complexitatea sa va fi O(3), nu este uimitor.

termenul trie provine din cuvântul regăsire, deoarece face recuperarea unui șir din colecția de șiruri foarte ușoară. Trie este, de asemenea, numit ca Prefix copac.

în Trie rădăcina este goală și fiecare nod copil conține un singur caracter. Deci, numărul de noduri copil, un anumit nod poate avea depinde de numărul de alfabete într-o anumită limbă. Să presupunem că folosim încercarea noastră pentru a stoca cuvinte în limba engleză, atunci fiecare nod va avea 26 de noduri copil.

în imaginea de mai sus am arătat doar 5 noduri copil, dar în rădăcină reală va avea 26 noduri copil, unul pentru fiecare alfabet.

acum, să vedem dacă trebuie să reprezentăm câteva șiruri în structura de date trie, atunci cum va arăta. Să presupunem că trebuie ă reprezentăm bile, cheli, mașini, piici și câini în încercări. Acest lucru va arăta așa cum se arată mai jos. În imaginea de mai jos, nodurile portocalii înseamnă sfârșitul cuvântului.

aceasta a fost introducerea a ceea ce este Trie, dar partea principală este modul în care trie poate fi implementat. Vom arăta cum Trie poate fi implementat mai jos.

fiecare nod din Trie trebuie să conțină două informații.

1. un steag boolean care spune că acest nod este sfârșitul unui cuvânt.
2. o matrice de dimensiune 26 (depinde de limba utilizată. 26 este pentru limba engleză). Fiecare index din această matrice indică un alt nod.

Să presupunem că fiecare nod din Trie este reprezentat de clasa TrieNode. Clasa TrieNode va avea două câmpuri:

1. isEnd: câmp Boolean.
2. copil: o serie de tip TrieNode.

apoi, vom avea o clasă Trie care va conține Inserare, căutare și metoda startsWith.

Să vedem cum va funcționa inserția pas cu pas. Trebuie să introducem piici în încercarea Noa tră.

1. inițial avem doar nod rădăcină. Toate indexurile din matrice sale conține NULL și isEnd pavilion este, de asemenea, fals.

2. Vom alege primul caracter din cat i. e c. acum indicele în matrice va fi 2. Dacă nu sunteți conștienți, atunci vom găsi indicele de orice alfabet în matrice de a face char-‘a’. Procedând astfel, indicele a este 0, b este 1, c este 2 și așa mai departe. Mergem la indexul 2 al matricei și îi atribuie un nou nod.

3. Acum ne mutăm indicatorul la al doilea nod. Al doilea alfabet în cat este un. așa că inițializăm indexul 0 la nod nou.

4. Mutăm indicatorul la nodul următor. Următorul alfabet în cat este t. indicele t este 19. Inițializăm indexul 19 la nod nou.

5. Trecem la nodul următor . Acum nu mai este lăsat să fie introdus alfabetul. Așa că marcăm acest nod ca sfârșit.

mai jos este codul java pentru metoda 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;
}

mai jos este soluția completă Java pentru acest program cu căutare și metoda 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;
}
}