Implement a trie with insert, search, and startsWith methods.
Note: You may assume that all inputs are consist of lowercase letters a-z.
Subscribe to see which companies asked this question.
public class Trie { private class node{ boolean mark; char val; node(char mchar){ val=mchar; } node[] children=new node[26]; } private node root; public Trie() { root = new node(' '); } public void insert(String word) { node temp=root; for(int i=0;i<word.length();i++){ char mchar=word.charAt(i); if(temp.children[mchar-'a']==null){ temp.children[mchar-'a']=new node(mchar); } temp=temp.children[mchar-'a']; } temp.mark=true; } public boolean search(String word) { node temp=root; for(int i=0;i<word.length();i++){ char mchar=word.charAt(i); if(temp.children[mchar-'a']==null){ return false; } temp=temp.children[mchar-'a']; } return temp.mark; } public boolean startsWith(String prefix) { node temp=root; for(int i=0;i<prefix.length();i++){ char mchar=prefix.charAt(i); if(temp.children[mchar-'a']==null){ return false; } temp=temp.children[mchar-'a']; } return true; } }