Given some dictionary list of words ("foo", "bar", "waz"), implement two functions:
setupDictionary();
 -> This can take reasonable time to execute- it should populate and optionally preprocess the dictionary

isMember(word);
 -> This needs to be fast. Return true if the given word is in the dictionary.

Examples:

isMember("foo"); // true
isMember("f.o"); // true
isMember("w.."); // true
isMember(".."); // false
isMember("blah"); // false

==

Setup  O(1)
Set<- add

isMember O(n)

  Setup O(n)
  root->{f}->{o}->{o}-true

  isMember O(len(n)) + O(1) + O(1) "foo".length
  O(1) + O(map.size()) + O(map.size()) = O(max(map.size()) -> O(n)


  class TrieNode<T>{
    Map<T, TrieNode> children;
    boolean end_of_list;
  }
  TrieNode<Character> root = new TrieNode();
  public void setupDictionary(String input) throws Exception{
    if(input==null){
      throw new Exception("input is null");
    }
    TrieNode curr = root;
    for(int i=0; i<input.length(); i++){
        if(curr.children.containsKey(input.charAt(i)){
          curr = curr.children.get(input.charAt(i));
        }else{
          TrieNode<Character> newNode = new TrieNode();
          curr.children.put(input.charAt(i), newNode);
          curr = newNode;
        }
    }
    curr.end_of_list = true;
  }
  public boolean isMember(String input, TrieNode curr){
    for(int i=0; i<input.length(); i++){
      if(input.charAt(i) != "."){
         if(!curr.children.containsKey(input.charAt(i)){
           return false;
         }else{
           curr = curr.children.get(input.charAt(i));
         }
      }else{
        for(Character c:curr.children.keySet()){
            isMember(input.substring(i+1),curr.children.get(c));
        }
      }
    }
    return true;
  }

what: insert "foo"
output: root{f}->newNode{o}->newNode{o}->newNode{end_of_list=true}