共计 1951 个字符，预计需要花费 5 分钟才能阅读完成。
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.
Example:addWord(“bad”)addWord(“dad”)addWord(“mad”)search(“pad”) -> falsesearch(“bad”) -> truesearch(“.ad”) -> truesearch(“b..”) -> trueNote:You may assume that all words are consist of lowercase letters a-z.
难度：medium
题目：设计数据结构支持以下两操作：void addWord(word)bool search(word)search(word) 可以查单词或包含. 的正则表达式。. 可以表示任何单个字符。
注意：你可以假定所有单词仅由小写字母组成。
思路：Tire Tree, DFS
Runtime: 94 ms, faster than 89.57% of Java online submissions for Add and Search Word – Data structure design.
class WordDictionary {
private TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
char c = word.charAt(0);
int i = 0, idx = 0;
TrieNode ptr = root;
for (; i < word.length(); i++, ptr = ptr.next[idx]) {
idx = word.charAt(i) – ‘a’;
if (null == ptr.next[idx]) {
ptr.next[idx] = new TrieNode();
}
}
ptr.isWord = true;
}
// dfs
/** 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 search(word, 0, root);
}
public boolean search(String word, int idx, TrieNode beginNode) {
if (idx >= word.length() || null == beginNode) {
return false;
}
TrieNode node = null;
int c = word.charAt(idx), cIdx = c – ‘a’;
if (‘.’ == c) {
boolean result = false;
for (int i = 0; i < 26; i++) {
node = beginNode.next[i];
if (null == node) {
continue;
}
if ((idx + 1) == word.length() && node.isWord) {
return true;
}
result = result || search(word, idx + 1, beginNode.next[i]);
}
return result;
}
// c is not equal to ‘.’
node = beginNode.next[cIdx];
if (null == node) {
return false;
}
if ((idx + 1) == word.length()) {
return node.isWord;
}
return search(word, idx + 1, beginNode.next[cIdx]);
}
public static class TrieNode {
public boolean isWord;
public TrieNode[] next = new TrieNode[26];
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
