package design;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by Goutham Vidya Pradhan on 7/3/2017.
 * Implement a trie with insert, search, and startsWith methods.

 Note:
 You may assume that all inputs are consist of lowercase letters a-z.
 */
public class Trie {

    private Map<Character, Trie> map;
    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        Trie trie = new Trie();
        trie.insert("boxing");
        trie.insert("box");
        System.out.println(trie.search("boxing"));
        System.out.println(trie.startsWith("box"));
        System.out.println(trie.search("box"));
    }

    /** Initialize your data structure here. */
    public Trie() {
        map = new HashMap<>();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        if(word != null){
            add(0, word, word.length());
        }
    }

    private void add(int i, String word, int length){
        if(i < length){
            char c = word.charAt(i);
            Trie subTrie = map.get(c);
            if(subTrie == null){
                subTrie = new Trie();
                map.put(c, subTrie);
            }
            subTrie.add(i + 1, word, length);
        }
        else map.put(null, new Trie()); //use null to indicate end of string
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if(word != null){
            return search(0, word, word.length());
        }
        return false;
    }

    private boolean search(int i, String word, int length){
        if(i < length){
            char c = word.charAt(i);
            Trie subTrie = map.get(c);
            if(subTrie == null)
                return false;
            return subTrie.search(i + 1, word, length);
        }
        return map.containsKey(null);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if(prefix != null){
            return startsWith(0, prefix, prefix.length());
        }
        return false;
    }

    private boolean startsWith(int i, String prefix, int length){
        if(i < length){
            char c = prefix.charAt(i);
            Trie subTrie = map.get(c);
            if(subTrie == null)
                return false;
            return subTrie.startsWith(i + 1, prefix, length);
        }
        else return true;
    }

}