Find Prefix String Using Trie Tree

import java.util.HashMap;/** * Created by jzhang21 on 1/20/15. */public class TrieTree { public HashMap<Character, TrieTree> sons = new HashMap<Character,TrieTree>(); public boolean isEndWord = false; public String prefix = ""; public void insert(String str){ insertStr(str,0, this); } private void insertStr(String str, int index, TrieTree node){ if(str.length() == index){ return; } TrieTree next = null; if(node.sons.containsKey(str.charAt(index))){ next = node.sons.get(str.charAt(index)); }else{ next = new TrieTree(); } if(str.length() == index+1){ next.isEndWord = true; } node.sons.put(str.charAt(index),next); insertStr(str,index+1,next); } public boolean isWord(String str){ if(!sons.containsKey(str.charAt(0))){ return false; }else{ if(str.length() == 1){ TrieTree node = sons.get(str.charAt(0)); return node.isEndWord; }else{ return isWordFor(str.substring(1), sons.get(str.charAt(0))); } } } public boolean isWordFor(String str, TrieTree node){ if(!node.sons.containsKey(str.charAt(0))){ return false; }else{ if(str.length() == 1){ TrieTree next = node.sons.get(str.charAt(0)); return next.isEndWord; }else{ return isWordFor(str.substring(1), node.sons.get(str.charAt(0))); } } } public void getPrefix(String str, boolean isFirst){ if(isFirst){ this.prefix = str; insert(str); }else{ if(sons.containsKey(str.charAt(0))){ getPrefixFor(str, 1, sons.get(str.charAt(0)) ); }else{ this.prefix = ""; } } } public void getPrefixFor(String str, int index, TrieTree node){ if(str.length() == index){ if(str.length() < prefix.length()){ prefix = str; } return; } if(node.sons.containsKey(str.charAt(index))){ getPrefixFor(str,index+1,node.sons.get(str.charAt(index))); }else{ String tmp = str.substring(0,index); if(tmp.length()<prefix.length()){ prefix = tmp; } } }}

public class Solution{ public static void main(String[] args){ TrieTree root = new TrieTree(); root.insert("abcdefg"); root.insert("abcfj"); root.insert("abe"); root.insert("ab"); System.out.println(root.isWord("ab")); System.out.println(root.isWord("abe")); System.out.println(root.isWord("abcfj")); System.out.println(root.isWord("abd")); System.out.println(root.isWord("abcg")); TrieTree prefixTree = new TrieTree(); prefixTree.getPrefix("abcdefg",true); prefixTree.getPrefix("abcfj",false); prefixTree.getPrefix("abe", false); prefixTree.getPrefix("ab",false); System.out.println(prefixTree.prefix); }}