leetcode 链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/

题目

image.png

解法

题目限定了字母为小写字母 a-z，所以可以创建一个大小为 26 的数组，每个数组位置代表一个字母

  1. public class Trie {
  2.     // 根节点
  3.     private final Node root;
  5.     private class Node {
  6.         private static final int size = 26;
  7.         // 当前节点是否为某个单词的末位
  8.         boolean isWord;
  9.         // 指向子节点
  10.         Node[] next;
  12.         public Node(boolean isWord) {
  13.             this.isWord = isWord;
  14.             next = new Node[size];
  15.         }
  17.         public Node() {
  18.             this(false);
  19.         }
  21.         public boolean containsKey(char ch) {
  22.             return next[ch - 'a'] != null;
  23.         }
  25.         public Node get(char ch) {
  26.             return next[ch - 'a'];
  27.         }
  29.         public void put(char ch, Node node) {
  30.             next[ch - 'a'] = node;
  31.         }
  32.     }
  34.     public Trie() {
  35.         this.root = new Node();
  36.     }
  38.     /**
  39.      * Inserts a word into the trie.
  40.      */
  41.     public void insert(String word) {
  42.         Node curr = root;
  43.         for (int i = 0; i < word.length(); i++) {
  44.             char ch = word.charAt(i);
  45.             if (!curr.containsKey(ch)) {
  46.                 curr.put(ch, new Node());
  47.             }
  48.             curr = curr.get(ch);
  49.         }
  50.         curr.isWord = true;
  51.     }
  53.     /**
  54.      * Returns if the word is in the trie.
  55.      */
  56.     public boolean search(String word) {
  57.         Node curr = root;
  58.         for (int i = 0; i < word.length(); i++) {
  59.             char ch = word.charAt(i);
  60.             if (!curr.containsKey(ch)) {
  61.                 return false;
  62.             }
  63.             curr = curr.get(ch);
  64.         }
  65.         return curr.isWord;
  66.     }
  68.     /**
  69.      * Returns if there is any word in the trie that starts with the given prefix.
  70.      */
  71.     public boolean startsWith(String prefix) {
  72.         Node curr = root;
  73.         for (int i = 0; i < prefix.length(); i++) {
  74.             char ch = prefix.charAt(i);
  75.             if (!curr.containsKey(ch)) {
  76.                 return false;
  77.             }
  78.             curr = curr.get(ch);
  79.         }
  80.         return true;
  81.     }
  82. }