package org.wesome.dsalgo;
import lombok.Data;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
public class Autocomplete {
private Node trie;
public Autocomplete(String[] wordList) {
trie = new Node("");
for (String word : wordList) {
insertWord(word);
}
}
private void insertWord(String word) {
/* Iterate through each character in the string. If the character is not already in the trie then add it */
Node curr = trie;
for (int indx = 0; indx < word.length(); indx++) {
char ch = word.charAt(indx);
/* if current children hashmap doesn't contain the letter */
if (!curr.children.containsKey(ch)) {
curr.children.put(ch, new Node(word.substring(0, indx + 1)));
}
curr = curr.children.get(ch);
/* if current character is last of word, it means it'word a complete word */
if (indx == word.length() - 1) {
curr.isWord = true;
}
}
}
/* Find all words in trie that start with prefix */
public List<String> getWordsForPrefix(String prefix) {
List<String> results = new LinkedList<>();
// Iterate to the end of the prefix
Node curr = trie;
for (char ch : prefix.toCharArray()) {
if (curr.children.containsKey(ch)) {
curr = curr.children.get(ch);
} else {
return results;
}
}
// At the end of the prefix, find all child words
findAllChildWords(curr, results);
return results;
}
// recursively iterate through find every child word
private void findAllChildWords(Node node, List<String> results) {
if (node.isWord) {
results.add(node.prefix);
}
for (Character ch : node.children.keySet()) {
findAllChildWords(node.children.get(ch), results);
}
}
@Data
private class Node {
String prefix;
HashMap<Character, Node> children;
/* Does this node represent the last character in a word? */ boolean isWord;
private Node(String prefix) {
this.prefix = prefix;
this.children = new HashMap<>();
}
}
}