题目

Design a data structure that supports the following two operations:

  1. void addWord(word)
  2. bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

  1. addWord("bad")
  2. addWord("dad")
  3. addWord("mad")
  4. search("pad") -> false
  5. search("bad") -> true
  6. search(".ad") -> true
  7. search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

题意

设计一个数据结构，支持插入单词和搜索单词两个操作。其中，搜索单词的参数可以是一个包含通配符”.”的正则。

思路

和 0208. Implement Trie (Prefix Tree) (M) 一样使用字典树。不同之处在于当搜索字符为”.”时，要查找所有出现过的字母。

代码实现

Java

  1. class WordDictionary {
  2.     Node root;
  4.     /** Initialize your data structure here. */
  5.     public WordDictionary() {
  6.         root = new Node();
  7.     }
  9.     /** Adds a word into the data structure. */
  10.     public void addWord(String word) {
  11.         Node p = root;
  12.         for (char c : word.toCharArray()) {
  13.             if (p.children[c - 'a'] == null) {
  14.                 p.children[c - 'a'] = new Node();
  15.             }
  16.             p = p.children[c - 'a'];
  17.         }
  18.         p.end = true;
  19.     }
  21.     /**
  22.      * Returns if the word is in the data structure. A word could contain the dot
  23.      * character '.' to represent any one letter.
  24.      */
  25.     public boolean search(String word) {
  26.         return search(word, 0, root);
  27.     }
  29.     private boolean search(String word, int index, Node p) {
  30.         if (index == word.length()) {
  31.             return p.end;
  32.         }
  34.         char c = word.charAt(index);
  35.         if (c == '.') {
  36.             for (Node next : p.children) {
  37.                 if (next != null && search(word, index + 1, next)) {
  38.                     return true;
  39.                 }
  40.             }
  41.             return false;
  42.         } else {
  43.             return p.children[c - 'a'] != null ? search(word, index + 1, p.children[c - 'a']) : false;
  44.         }
  45.     }
  46. }
  48. class Node {
  49.     Node[] children = new Node[26];
  50.     boolean end;
  51. }
  53. /**
  54.  * Your WordDictionary object will be instantiated and called as such:
  55.  * WordDictionary obj = new WordDictionary(); obj.addWord(word); boolean param_2
  56.  * = obj.search(word);
  57.  */