Trie

import java.util.*;

class MyCode {
    public static void main (String[] args) {
        String[] dict = {"cat","car","cart","catheter","bat","balance","bot","apple"};
    Trie trie = new Trie();

    for(String word : dict) trie.addWord(word);
    System.out.println(trie.autocomplete("car"));
    }
}


class TrieNode {
  public char value;
  public boolean endWord;
  public HashMap<Character, TrieNode> children;

  public TrieNode(char ch) {
    this.value = ch;
    this.endWord = false;
    this.children = new HashMap<>();
  }
}

class Trie {
  TrieNode root;

  public Trie() {
    this.root = new TrieNode('\u0000');
  }

  public void addWord(String word) {
    //Grab root node into current node pointer
    TrieNode curr = this.root;
    //Loop over chars in word
    for(Character ch: word.toCharArray()){
      //Check if child char not exists in children of curr trienode
      if(!curr.children.containsKey(ch)) {
        //Add new trie node for child char to children of curr trienode
        curr.children.put(ch, new TrieNode(ch));
      }
      //Move to the trienode associated with the child char
      curr = curr.children.get(ch);
    }
    //Set endWord flag for curr pointer to true
    curr.endWord = true;
  }

  public TrieNode getPrefixEndNode(String prefix) {
    //Grab root node into current node pointer
    TrieNode curr = this.root;
    //Loop over chars in word
    for(Character ch: prefix.toCharArray()){
      //Check if child char not exists in children of curr trienode
      if(!curr.children.containsKey(ch)) {
        return null;
      }
      //Move to the trienode associated with the child char
      curr = curr.children.get(ch);
    }
    return curr;
  }

  public boolean prefixExists(String prefix) {
    return getPrefixEndNode(prefix) != null;
  }

  public ArrayList<String> autocomplete(String prefix) {
    //Init empty arraylist
    ArrayList<String> result = new ArrayList<>();
    //Get the prefix end node
    TrieNode endPrefixNode = getPrefixEndNode(prefix);

    //if prefix end node not null, dfs from node
    if(endPrefixNode != null) {
      //dfs with prefix string, end prefix node, result list, null char literal
      dfs(prefix, endPrefixNode, result, '\u0000');
    }
    // return result list
    return result;

  }

  private void dfs(String currStr, TrieNode currNode, ArrayList<String> result, char currCh){
    //Add currCh to currStr
    currStr += currCh;
    //Base case when endWord flag reached
    if(currNode.endWord){
      //Add currStr to results
      result.add(currStr);
    }

    //Loop through child chars of currNode
    for(TrieNode childNode: currNode.children.values()) {
      //dfs on currStr, child TrieNode, result arraylist, child char
      dfs(currStr, childNode, result, childNode.value);
    }

  }

  /*

  Given 3 different systems with dictionaries of words, come up with efficient way of storing data

  */
}