Interview Question
Country: India
Interview Type: In-Person
Here is the following code.
package pray;
import java.util.HashMap;
import java.util.Map;
public class Trie{
public static class TrieNode{
char c;
HashMap <Character,TrieNode> children = new HashMap<Character,TrieNode>();
boolean isLeaf;
public TrieNode(){
}
public TrieNode(char c){
this.c = c;
}
}
private TrieNode root;
public Trie(){
root = new TrieNode();
}
public void insert(String word){
HashMap<Character,TrieNode> children = root.children;
for(int i=0; i<word.length();i++){
char c = word.charAt(i);
TrieNode t;
if(children.containsKey(c)){
t = children.get(c);
}else{
t = new TrieNode(c);
children.put(c,t);
}
children = t.children;
if(i==word.length()-1){
t.isLeaf = true;
}
}
}
public boolean search(String word){
TrieNode t = searchNode(word);
if(t!=null && t.isLeaf){
return true;
}else{
return false;
}
}
public boolean startsWith(String prefix){
if(searchNode(prefix)==null){
return false;
}else{
return true;
}
}
private TrieNode searchNode(String str) {
Map<Character, TrieNode> children = root.children;
TrieNode t = null;
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(children.containsKey(c)){
t = children.get(c);
children = t.children;
}else{
return null;
}
}
return t;
}
public static void main(String[] args){
Trie t = new Trie();
t.insert("get");
t.insert("hi");
t.insert("hello");
t.insert("computer");
t.insert("communication");
t.insert("communist");
System.out.println(t.startsWith("com"));
}
}
We can use Tries
- revanthpobala November 03, 2015