Add and Search Word - Data structure design

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.

For 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.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Solution:

  1. public class WordDictionary {
  3.   Trie trie = new Trie();
  5.   // Adds a word into the data structure.
  6.   public void addWord(String word) {
  7.     trie.insert(word);
  8.   }
  10.   // Returns if the word is in the data structure. A word could
  11.   // contain the dot character '.' to represent any one letter.
  12.   public boolean search(String word) {
  13.     return trie.search(word);
  14.   }
  16.   class TrieNode {
  17.     // Initialize your data structure here.
  18.     char c;
  19.     boolean isLeaf;
  20.     Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
  22.     public TrieNode() {}
  23.     public TrieNode(char c) { this.c = c; }
  24.   }
  26.   public class Trie {
  27.     private TrieNode root;
  29.     public Trie() {
  30.       root = new TrieNode();
  31.     }
  33.     // Inserts a word into the trie.
  34.     public void insert(String word) {
  35.       Map<Character, TrieNode> children = root.children;
  37.       for (int i = 0; i < word.length(); i++) {
  38.         char c = word.charAt(i);
  40.         if (!children.containsKey(c))
  41.           children.put(c, new TrieNode(c));
  43.         TrieNode t = children.get(c);
  45.         if (i == word.length() - 1) 
  46.           t.isLeaf = true;
  48.         children = t.children;
  49.       }
  50.     }
  52.     // Returns if the word is in the trie.
  53.     public boolean search(String word) {
  54.       return dfs(root, word, 0);
  55.     }
  57.     private boolean dfs(TrieNode node, String word, int index) {
  58.       if (node == null || index == word.length() && !node.isLeaf)
  59.         return false;
  61.       if (node.isLeaf && index == word.length())
  62.         return true;
  64.       char c = word.charAt(index);
  66.       if (c == '.') {
  67.         for (char ch = 'a'; ch <= 'z'; ch++) {
  68.           if (dfs(node.children.get(ch), word, index + 1))
  69.             return true;
  70.         }
  72.         return false;
  73.       } else {
  74.         return dfs(node.children.get(c), word, index + 1);
  75.       }
  76.     }
  77.   }
  78. }
  80. // Your WordDictionary object will be instantiated and called as such:
  81. // WordDictionary wordDictionary = new WordDictionary();
  82. // wordDictionary.addWord("word");
  83. // wordDictionary.search("pattern");