208. 实现 Trie (前缀树)

  1. class Trie {
  2.     class TrieNode {
  3.         public TrieNode[] children;
  4.         public boolean isEnd;
  6.         public TrieNode() {
  7.             children = new TrieNode[26];
  8.             isEnd = false;
  9.         }
  10.     }
  12.     private TrieNode root;
  15.     /** Initialize your data structure here. */
  16.     public Trie() {
  17.         root = new TrieNode();
  18.     }
  20.     /** Inserts a word into the trie. */
  21.     public void insert(String word) {
  22.         TrieNode node = root;
  23.         if (word == null)
  24.             return;
  26.         char[] words = word.toCharArray();
  27.         for (char ch : words) {
  28.             if (node.children[ch - 'a'] == null)
  29.                 node.children[ch - 'a'] = new TrieNode();
  31.             node = node.children[ch - 'a'];
  32.         }
  33.         node.isEnd = true;
  34.     }
  36.     /** Returns if the word is in the trie. */
  37.     public boolean search(String word) {
  38.         TrieNode node = root;
  39.         if (word == null || word.length() == 0)
  40.             return true;
  42.         char[] words = word.toCharArray();
  44.         for (char ch : words) {
  45.             if (node.children[ch - 'a']  == null)
  46.                 return false;
  48.             node = node.children[ch - 'a'];
  49.         }
  50.         return node.isEnd;
  51.     }
  53.     /** Returns if there is any word in the trie that starts with the given prefix. */
  54.     public boolean startsWith(String prefix) {
  55.         TrieNode node = root;
  56.         if (prefix == null || prefix.length() == 0)
  57.             return true;
  59.         char[] pres = prefix.toCharArray();
  61.         for (char ch : pres) {
  62.             if (node.children[ch - 'a'] == null)
  63.                 return false;
  65.             node = node.children[ch - 'a'];
  66.         }
  68.         return true;
  69.     }
  70. }
  72. /**
  73.  * Your Trie object will be instantiated and called as such:
  74.  * Trie obj = new Trie();
  75.  * obj.insert(word);
  76.  * boolean param_2 = obj.search(word);
  77.  * boolean param_3 = obj.startsWith(prefix);
  78.  */