Autocomplete Word With Prefix - Tries

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()
}

 

follow us on