image.png

    字典树(前缀树)

    1. public class Trie {
    2.     private Trie[] children;
    3.     private boolean isEnd;
    5.     /**
    6.      * Initialize your data structure here.
    7.      */
    8.     public Trie() {
    9.         children = new Trie[26];
    10.         isEnd = false;
    11.     }
    13.     /**
    14.      * Inserts a word into the trie.
    15.      */
    16.     public void insert(String word) {
    17.         Trie node = this;
    18.         for (int i = 0; i < word.length(); i++) {
    19.             char ch = word.charAt(i);
    20.             int index = ch - 'a';
    21.             if (node.children[index] == null) {
    22.                 node.children[index] = new Trie();
    23.             }
    24.             node = node.children[index];
    25.         }
    26.         node.isEnd = true;
    27.     }
    29.     /**
    30.      * Returns if the word is in the trie.
    31.      */
    32.     public boolean search(String word) {
    33.         Trie node = searchPrefix(word);
    34.         return node != null && node.isEnd;
    35.     }
    37.     private Trie searchPrefix(String prefix) {
    38.         Trie node = this;
    39.         for (int i = 0; i < prefix.length(); i++) {
    40.             char ch = prefix.charAt(i);
    41.             int index = ch - 'a';
    42.             if (node.children[index] == null) {
    43.                 return null;
    44.             }
    45.             node = node.children[index];
    46.         }
    47.         return node;
    48.     }
    50.     /**
    51.      * Returns if there is any word in the trie that starts with the given prefix.
    52.      */
    53.     public boolean startsWith(String prefix) {
    54.         return searchPrefix(prefix) != null;
    55.     }
    56. }