Leetcode: Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
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:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

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

click to show hint.

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

Understand the problem:
Use Trie + DFS

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

public class WordDictionary {     class TrieNode {         char val;         boolean leaf;         TrieNode[] children;                   public TrieNode() {             this.val = '\0';             this.leaf = false;             this.children = new TrieNode[26];         }                   public TrieNode(char val, boolean leaf) {             this.val = val;             this.leaf = leaf;             this.children = new TrieNode[26];         }     }           private TrieNode root = new TrieNode();     private TrieNode dummyRoot = root;           // Adds a word into the data structure.     public void addWord(String word) {         TrieNode curr = root;         int offset = 'a';         int i = 0;         for (i = 0; i < word.length(); i++) {             char character = word.charAt(i);             if (curr.children[character - offset] == null) {                 curr.children[character - offset] =                     new TrieNode(character, i == word.length() - 1 ? true : false);             } else {                 if (i == word.length() - 1) {                     curr.children[character - offset].leaf = true;                 }             }                           curr = curr.children[character - offset];         }     }       // Returns if the word is in the data structure. A word could     // contain the dot character '.' to represent any one letter.     public boolean search(String word) {         if (word == null || word.length() == 0) {             return false;         }                   TrieNode curr = root;         int offset = 'a';         for (int i = 0; i < word.length(); i++) {             char character = word.charAt(i);             if (character != '.') {                 if (curr.children[character - offset] == null) {                     return false;                 }                 curr = curr.children[character - offset];             } else {                 // DFS                 for (int j = 0; j < 26; j++) {                     if (curr.children[j] != null) {                         if (i == word.length() - 1 && curr.children[j].leaf) {                             root = dummyRoot;                             return true;                         }                                                   root = curr.children[j];                         if (search(word.substring(i + 1))) {                             root = dummyRoot;                             return true;                         }                     }                 }                 root = dummyRoot;                 return false;             }         }                   if (curr != null && curr.leaf == false) {             return false;         }                   return true;     } }   // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary = new WordDictionary(); // wordDictionary.addWord("word"); // wordDictionary.search("pattern");

Update on 10/19/15:
Updated neat version without saving the value for a TrieNode. 
There are mainly two tricks in the problem:
  -- The first trick is, in the DFS, we need to change the root of the Trie, and don't forget to change it back. 
  -- The second trick is, when we tried all 26 possibilities without getting an answer, we must return false instead. 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

public class WordDictionary {     private Trie trie = new Trie();           // Adds a word into the data structure.     public void addWord(String word) {         trie.add(word);     }       // Returns if the word is in the data structure. A word could     // contain the dot character '.' to represent any one letter.     public boolean search(String word) {         return trie.search(word);     }           class Trie {         private TrieNode root = new TrieNode();         private TrieNode rootCopy = root;                   // Add a word         void add(String word) {             TrieNode p = root;                           for (int i = 0; i < word.length(); i++) {                 char c = word.charAt(i);                 if (p.children[c- 'a'] != null) {                     p = p.children[c - 'a'];                 } else {                     p.children[c - 'a'] = new TrieNode();                     p = p.children[c - 'a'];                 }                                   if (i == word.length() - 1) {                     p.leaf = true;                 }             }         }                   boolean search(String word) {             TrieNode p = root;                           for (int i = 0; i < word.length(); i++) {                 char c = word.charAt(i);                                   if (c == '.') {                     for (int j = 0; j < 26; j++) {                         if (p.children[j] != null) {                             // Change the root pointer                             root = p.children[j];                                                           if (search(word.substring(i + 1))) {                                 root = rootCopy;                                 return true;                             }                                                           // Change back the root pointer                             root = rootCopy;                         }                     }                     // If none of them get true, return false;                                       return false;                 } else {                     if (p.children[c - 'a'] == null) {                         return false;                     }                     p = p.children[c - 'a'];                 }             }                           if (!p.leaf) {                 return false;             }                           return true;         }     }           class TrieNode {         TrieNode[] children;         boolean leaf;                   public TrieNode() {             children = new TrieNode[26];         }     } }   // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary = new WordDictionary(); // wordDictionary.addWord("word"); // wordDictionary.search("pattern");