2017年9月27日星期三

Trie Implementation

 public class Trie {  
      static final int ALPHABET_SIZE = 26;  
      static class TrieNode {  
           TrieNode[] children = new TrieNode[ALPHABET_SIZE];  
           boolean isEndOfWord;  
           TrieNode() {  
                isEndOfWord = false;  
                for (int i = 0; i < ALPHABET_SIZE; i++) {  
                     children[i] = null;  
                }  
           }  
      }  
      static TrieNode root;  
      // if not parent, inserts key into trie  
      // if the key is prefix of trie node, just mark leaf node  
      static void insert(String key) {  
           int level;  
           int length = key.length();  
           int index;  
           TrieNode pCrawl = root;  
           for (level = 0; level < length; level++) {  
                index = key.charAt(level) - 'a';  
                if (pCrawl.children[index] == null) {  
                     pCrawl.children[index] = new TrieNode();  
                }  
                pCrawl = pCrawl.children[index];  
           }  
           // mark the last node as leaf  
           pCrawl.isEndOfWord = true;  
      }  
      // Returns true if key presnts in trie, else false  
      static boolean search(String key) {  
           int level;  
           int length = key.length();  
           int index;  
           TrieNode pCrawl = root;  
           for (level = 0; level < length; level++) {  
                index = key.charAt(level) - 'a';  
                if (pCrawl.children[index] == null) {  
                     return false;  
                }  
                pCrawl = pCrawl.children[index];  
           }  
           return pCrawl != null && pCrawl.isEndOfWord;  
      }   
 }