阅读排行
首页 > 技术文章

LinkCode刷题 字典树

  1. class TrieNode {  
  2.     // Initialize your data structure here.  
  3.     char c;  
  4.     boolean leaf;  
  5.     HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();  
  6.       
  7.     public TrieNode(char c) {  
  8.         this.c = c;  
  9.     }  
  10.           
  11.     public TrieNode(){};  
  12. }  
  13.   
  14. public class Trie {  
  15.     private TrieNode root;  
  16.   
  17.     public Trie() {  
  18.         root = new TrieNode();  
  19.     }  
  20.   
  21.     // Inserts a word into the trie.  
  22.     public void insert(String word) {  
  23.         Map<Character, TrieNode> children = root.children;  
  24.         for(int i=0; i<word.length(); i++) {  
  25.             char c = word.charAt(i);  
  26.             TrieNode t;  
  27.             if(children.containsKey(c)) {  
  28.                 t = children.get(c);  
  29.             } else {  
  30.                 t = new TrieNode(c);  
  31.                 children.put(c, t);  
  32.             }  
  33.             children = t.children;  
  34.             if(i==word.length()-1) t.leaf=true;  
  35.         }  
  36.     }  
  37.   
  38.     // Returns if the word is in the trie.  
  39.     public boolean search(String word) {  
  40.         TrieNode t = searchNode(word);  
  41.         return t!=null && t.leaf;  
  42.     }  
  43.   
  44.     // Returns if there is any word in the trie  
  45.     // that starts with the given prefix.  
  46.     public boolean startsWith(String prefix) {  
  47.         return searchNode(prefix) != null;  
  48.     }  
  49.       
  50.     private TrieNode searchNode(String word) {  
  51.         Map<Character, TrieNode> children = root.children;  
  52.         TrieNode t = null;  
  53.         for(int i=0; i<word.length(); i++) {  
  54.             char c = word.charAt(i);  
  55.             if(!children.containsKey(c)) return null;  
  56.             t = children.get(c);  
  57.             children = t.children;  
  58.         }  
  59.         return t;  
  60.     }  
  61. }  
  62.   
  63. // Your Trie object will be instantiated and called as such:  
  64. // Trie trie = new Trie();  
  65. // trie.insert("somestring");  
  66. // trie.search("key");  
文章来自：http://www.cnblogs.com/zhaoprence/p/4937702.html
© 2021 jiaocheng.bubufx.com  联系我们
ICP备案：鲁ICP备09046678号-3