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<>();
}
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Test;
public class AutocompleteTest {
@Test
void autocompleteTest1() {
Autocomplete autocomplete = new Autocomplete(new String[]{"and", "ant", "bee", "bird", "cat", "cow", "dog"});
System.out.println(autocomplete.getWordsForPrefix("a"));
}
@Test
void autocompleteTest2() {
Autocomplete autocomplete = new Autocomplete(new String[]{"aunt", "area", "best", "ball", "card", "cool", "dust", "deal"});
System.out.println(autocomplete.getWordsForPrefix("a"));
}
}
plugins {
id 'java'
id "io.freefair.lombok" version "6.2.0"
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}