leetcode 链接：https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/

题目

image.png
image.png

解法

  1. public class WordDictionary {
  2.     private class Node {
  3.         private static final int size = 26;
  4.         // 当前节点是否为某个单词的末位
  5.         boolean isWord;
  6.         // 指向子节点
  7.         Node[] next;
  9.         public Node(boolean isWord) {
  10.             this.isWord = isWord;
  11.             next = new Node[size];
  12.         }
  14.         public Node() {
  15.             this(false);
  16.         }
  18.         public boolean containsKey(char ch) {
  19.             return next[ch - 'a'] != null;
  20.         }
  22.         public Node get(char ch) {
  23.             return next[ch - 'a'];
  24.         }
  26.         public void put(char ch, Node node) {
  27.             next[ch - 'a'] = node;
  28.         }
  29.     }
  31.     // 根节点
  32.     private final Node root;
  34.     /**
  35.      * Initialize your data structure here.
  36.      */
  37.     public WordDictionary() {
  38.         this.root = new Node();
  39.     }
  41.     /**
  42.      * Adds a word into the data structure.
  43.      */
  44.     public void addWord(String word) {
  45.         Node curr = root;
  46.         for (int i = 0; i < word.length(); i++) {
  47.             char ch = word.charAt(i);
  48.             if (!curr.containsKey(ch)) {
  49.                 curr.put(ch, new Node());
  50.             }
  51.             curr = curr.get(ch);
  52.         }
  53.         curr.isWord = true;
  54.     }
  56.     /**
  57.      * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
  58.      */
  59.     public boolean search(String word) {
  60.         return search(root, word, 0);
  61.     }
  63.     private boolean search(Node curr, String word, int index) {
  64.         if (word.length() == index) {
  65.             // 到达末尾
  66.             return curr.isWord;
  67.         }
  68.         char ch = word.charAt(index);
  70.         if (ch == '.') {
  71.             // 遍历所有的节点一一匹配，如果能够终止于true，说明能够匹配成功
  72.             for (Node node : curr.next) {
  73.                 if (node != null && search(node, word, index + 1)) {
  74.                     return true;
  75.                 }
  76.             }
  77.             return false;
  78.         } else if (!curr.containsKey(ch)) {
  79.             return false;
  80.         } else {
  81.             return search(curr.get(ch), word, index + 1);
  82.         }
  83.     }
  84. }