Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

 

 
class TrieNode {
    char c; 
    /*
     * Build a HashMap for Trie, where: 
     * key: a character of the input string 
     * value: sub-tree
     */
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>(); 
    boolean isLeaf; 
    
    public TrieNode() {} 
    
    public TrieNode(char c) {
        this.c = c; 
    }
}


public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        HashMap<Character, TrieNode> children = root.children;  
        
        //check each character of the string 
        for (int i = 0; i < word.length(); i++) {
            //for the ith character 
            char c = word.charAt(i); 
            //t is the node that corresponds to the ith character 
            TrieNode t; 
            //check if the HashMap contains the key c 
            if (children.containsKey (c)) {
                //if yes, get the sub-tree corresponding to the key c. 
                t = children.get(c); 
            } else {
                //if no, create a new TrieNode 
                t = new TrieNode(c); 
                //Put the new relationship set into the HashMap 
                children.put(c,t);
            }
            
            //update children. Now we need to check the next level 
            children = t.children; 
            
            //set leat node 
            if (i== word.length()-1) 
                t.isLeaf = true; 
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode t = searchNode(word);
        
        if (t != null && t.isLeaf) {
            return true; 
        } else {
            return false; 
        }
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if (searchNode(prefix) == null) {
            return false; 
        } else {
            return true; 
        }
    }
    
    public 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; 
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s