### 题目

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")
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.

### 标准的 单词查找树（Trie），复杂度 $O(len)$，len为单词的长度

Implement Trie (Prefix Tree)这一题里，已经证明了用普通 二叉树 也能在 $O(\log_{}{N})$ 时间内完成addWord()search()。 但二叉树的深度是以2为底对数 $O(\log_{2}{N})$

1. Array数组来储存TrieNode信息，比Map或者List更好。Array不但和Map一样能做到 $O(1)$ 时间内的随机访问，而且还可以不用储存字符信息char，因为数组的[1-26]的下标就代表了对应的字符。
2. 可以用一个boolean isEnd来标记单词的结尾。就可以知道比如ad到底表示一个完整的单词，还是只是add的一个子串。
3. boolean isEnd标记的地方，是在单词最后一个字符的下面一层。
单词：[add]

[0|1|2|3|4|5|...|23|24|25]                             (isEnd = false)
|
+-> [0|1|2|3|4|5|...|23|24|25]                        (isEnd = false)
|
+-> [0|1|2|3|4|5|...|23|24|25]             (isEnd = false)
|
+-> [0|1|2|3|4|5|...|23|24|25]  (isEnd = true)


public class TrieNode {
private TrieNode[] children = new TrieNode[26];
private boolean isEnd;
}


#### 具体代码如下

public class WordDictionary {
private static class Letter {
private Letter[] postfixs = new Letter[26];
private boolean isEnd;
}

Letter dummy = new Letter();

/** Adds a word into the data structure. */
Letter cur = dummy;
for (int i = 0; i < word.length(); i++) {
int offset = word.charAt(i) - 'a';
if (cur.postfixs[offset] == null) {
cur.postfixs[offset] = new Letter();
}
cur = cur.postfixs[offset];
}
cur.isEnd = true;
}

/** 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 dfs(word.toCharArray(),0,dummy);
}

/** Iterate the Prefix Tree with Depth First Search */
public boolean dfs(char[] word, int index, Letter curr) {
// base case
if (curr == null) { return false; } // too deep
if (index == word.length) { return curr.isEnd; }
// recursion
int offset = word[index] - 'a';
if (offset >= 0) { // [a-z]
return dfs(word,index+1,curr.postfixs[offset]);
} else { // [.]
for (Letter l : curr.postfixs) {
if (dfs(word,index+1,l)) { return true; }
}
}
return false;
}
}