Trie.java

import java.util.*;

public class Trie{
    class Node{
        int count;
        Node[] children;
        boolean isEnd;
        public Node(){
            this.children = new Node[26];
            this.count = 0;
            this.isEnd = false;
        }
    }
    public Node root;

    public Trie(){
        this.root = new Node();
    }

    public void insert(String s){
        Node cur = root;
        for(int i=0; i<s.length(); i++){
            int index = (int)s.charAt(i)-'a';
            if(cur.children[index]==null){
                cur.children[index]=new Node();
            }
            cur.count++;
            cur = cur.children[index];
        }
        cur.count++;
        cur.isEnd=true;
    }

    public void printNumStringsWithPref(String p){
        Node cur = root;
        for(int i=0; i<p.length(); i++){
            if(cur ==null){
                System.out.println(0);
                return;
            }
            cur = cur.children[p.charAt(i)-'a'];
        }
        if(cur==null){
            System.out.println(0);
            return;
        }
        System.out.println(cur.count);
    }

    public boolean isWord(String s){
        Node cur = root;
        for(int i=0; i<s.length(); i++){
            if(cur==null)
                return false;
            cur = cur.children[s.charAt(i)-'a'];
        }
        if(cur==null)
            return false;
        return cur.isEnd==true;
    }

    public String findLongestPrefixWord(String s){
        Node cur = root;
        int index = -1;
        for(int i=0; i<s.length(); i++){
            cur = cur.children[s.charAt(i)-'a'];
            if(cur==null){
                break;
            }
            if(cur.isEnd){
                index = i;

            }
        }
        return s.substring(0,index+1);
    }

    public void delete(Node n, String s, int index){
        if(index ==s.length())
            return;
        Node child = n.children[s.charAt(index)-'a'];
        if(index ==s.length()-1){
            child.isEnd=false;
        }

        delete(child, s, index+1);
        if(child.count==1){
            n.children[s.charAt(index)-'a']=null;
        }
        else{
            child.count--;
        }
    }
    public static void main(String[] args){
        Trie trie = new Trie();
        trie.insert("hello");
        trie.insert("hey");
        trie.insert("hi");
        trie.insert("app");
        trie.insert("applet");
        trie.insert("bla");
        trie.insert("blabla");
        trie.insert("wtf");
        trie.insert("wth");
        trie.insert("are");
        trie.insert("area");
        trie.insert("base");
        trie.insert("cat");
        trie.insert("cater");
        trie.insert("basement");
        trie.printNumStringsWithPref("a");
        System.out.println(trie.findLongestPrefixWord("heylohowareyou"));

    }

}