Thursday, August 20, 2015

Leetcode: Implement Trie (Prefix Tree)

Implement a trie with insertsearch, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
Understand the problem:

Trie is an efficient information retrieval data structure. Using trie, search complexities can be brought to optimal limit (key length). If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using trie, we can search the key in O(M) time. However the penalty is on trie storage requirements.

Insert and search costs O(key_length), however the memory requirements of trie isO(ALPHABET_SIZE * key_length * N) where N is number of keys in trie. There are efficient representation of trie nodes (e.g. compressed trie, ternary search tree, etc.) to minimize memory requirements of trie. The space complexity for BST is O(M * N). 

Now we consider the two major operations of a Trie: insert and search.
For the insert operation, we iterate through the inserted word. There are three cases to consider: 
  -- If the inserted character does not exist in the trie. Then create a new TrieNode. 
  -- If the inserted character exists, but not the leaf node. Then move on. 
  -- If the inserted character exists and is the leaf node. Mark the TrieNode as leaf. 

For the search operation, we iterate through the word to search. There are two cases to consider. 
  -- If not reached the end of the word, but the TrieNode is null, then return false; 
  -- If reached the end of the word, but the last TrieNode is not a leaf. Return false. 

Code (Java):
class TrieNode {
    // Initialize your data structure here.
    char val;
    boolean leaf;
    TrieNode[] children;
    
    public TrieNode(char val, boolean leaf) {
        this.val = val;
        this.leaf = leaf;
        children = new TrieNode[26];
    }
    
    public TrieNode() {
        val = '\0';
        children = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        int offset = 97;
        char[] wordArray = word.toCharArray();
        int len = wordArray.length;
        TrieNode curr = root;
        
        for (int i = 0; i < len; i++) {
            if (curr.children[wordArray[i] - offset] == null) {
                curr.children[wordArray[i] - offset] = new TrieNode(wordArray[i], 
                    i == len - 1 ? true : false);
            } else {
                if (i == len - 1) {
                    curr.children[wordArray[i] - offset].leaf = true;
                }
            }
            
            curr = curr.children[wordArray[i] - offset];
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        int offset = 97;
        char[] wordArray = word.toCharArray();
        int len = wordArray.length;
        TrieNode curr = root;
        int i = 0;
        for (i = 0; i < len; i++) {
            if (curr.children[wordArray[i] - offset] == null) {
                return false;
            }
            curr = curr.children[wordArray[i] - offset];
        }
        
        if (curr != null && !curr.leaf) {
            return false;
        }
        
        return true;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        int offset = 97;
        char[] prefixArray = prefix.toCharArray();
        int len = prefixArray.length;
        
        TrieNode curr = root;
        int i = 0;
        for (i = 0; i < len; i++) {
            if (curr.children[prefixArray[i] - offset] == null) {
                return false;
            }
            curr = curr.children[prefixArray[i] - offset];
        }
        
        return true;
    }
}
// Your Trie object will be instantiated and called as such: // Trie trie = new Trie(); // trie.insert("somestring"); // trie.search("key");




Update on 10/18/15:

For each Trie node, it does not need a val because its children denotes its value

Code (Java):
class TrieNode {
    // Initialize your data structure here.
    TrieNode[] children;
    boolean leaf; 
    public TrieNode() {
        children = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }
            
            if (i == word.length() - 1) {
                p.children[c - 'a'].leaf = true;
            }
            
            p = p.children[c - 'a'];
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            
            if (p.children[c - 'a'] == null) {
                return false;
            }
            
            p = p.children[c - 'a'];
        }
        
        if (!p.leaf) {
            return false;
        }
        
        return true;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            
            if (p.children[c - 'a'] == null) {
                return false;
            }
            
            p = p.children[c - 'a'];
        }
        
        return true;
    }
}

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

No comments:

Post a Comment