Berikut di bawah ini adalah kode dengan implementasi HashMap dari Trie. Tapi saya tidak yakin bagaimana menerapkan bagian pelengkapan otomatis. Saya melihat bagaimana orang menggunakan LinkedList untuk mengimplementasikan Trie, tapi saya ingin memahami dengan HashMap. Bantuan apa pun dihargai. Saya telah menempelkan kode di bawah ini untuk Trie saya.
Apakah ada cara untuk mencari awalan, lalu pergi ke akhir awalan dan mencari turunannya dan mengembalikannya sebagai string? Dan jika demikian, bagaimana cara mencapainya dengan menggunakan implementasi HashMap. Atau sebaiknya saya tidak melakukan ini dengan HashMap dan menggunakan LinkedList. Dan saya tidak yakin, mengapa yang satu lebih baik dari yang lain?
public class TrieNode {
Map<Character, TrieNode> children;
boolean isEndOfWord;
public TrieNode() {
isEndOfWord = false;
children = new HashMap<>();
}
}
public class TrieImpl {
private TrieNode root;
public TrieImpl() {
root = new TrieNode();
}
// iterative insertion into Trie Data Structure
public void insert(String word) {
if (searchTrie(word))
return;
TrieNode current = root;
for(int i=0; i<word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if(node == null) {
node = new TrieNode();
current.children.put(ch, node);
}
current = node;
}
current.isEndOfWord = true;
}
// search iteratively
public boolean searchTrie(String word) {
TrieNode current = root;
for(int i=0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if(node == null) {
return false;
}
current = node;
}
return current.isEndOfWord;
}
// delete a word recursively
private boolean deleteRecursive(TrieNode current, String word, int index) {
if(index == word.length()) {
if(!current.isEndOfWord) {
return false;
}
current.isEndOfWord = false;
return current.children.size() == 0;
}
char ch = word.charAt(index);
TrieNode node = current.children.get(ch);
if(node == null) {
return false;
}
boolean shouldDeleteCurrentNode = deleteRecursive(node, word, index+1);
if(shouldDeleteCurrentNode) {
current.children.remove(ch);
return current.children.size() == 0;
}
return false;
}
// calling the deleteRecursively function
public boolean deleteRecursive(String word) {
return deleteRecursive(root, word, 0);
}
public static void main(String[] args) {
TrieImpl obj = new TrieImpl();
obj.insert("amazon");
obj.insert("amazon prime");
obj.insert("amazing");
obj.insert("amazing spider man");
obj.insert("amazed");
obj.insert("alibaba");
obj.insert("ali express");
obj.insert("ebay");
obj.insert("walmart");
boolean isExists = obj.searchTrie("amazing spider man");
System.out.println(isExists);
}
}