题目
题目描述：
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary()初始化词典对象void addWord(word)将 word 添加到数据结构中，之后可以对它进行匹配bool search(word)如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。
示例：
题目解析
此题是需要设计一个数据结构用于存储单词，但是注意，插入的单词是普通的单词，但查找的时候可以使用 ‘.’ 进行通配。
- 这种题型很容易就想到用 字典树 (Trie) 这种数据结构实现。
而字典树的实现可以用两种：
- 链式动态实现：用一个 bool标记+指针索引 组成一个结点的结构体。
- 二维数组静态实现：二维数组的第一维代表一个结点，第二维代表指向下一个结点的指针索引，然后再用一个bool数组记录该位置的结点是否是终点。
链式和静态数组实现的优劣：
存储空间分析：
链式动态实现，所有的内存空间都被充分利用，而静态数组的实现并不能充分利用好所有的空间，有很多是被浪费了，所以链式动态实现是很节省空间的。
运行效率分析：
链式动态实现肯定是要慢于静态数组实现的，首先链式实现需要申请堆内存，而对堆内存的访问和申请是比栈内存要慢很多的，再者，静态数组只需要分配一次内存空间，而动态申请内存需要多次。所以静态数组实现效率是要高一些的。
解题代码
关键的解题思路在于查找，因为我们需要实现通配符的查找，直接用dfs进行查找。其余的操作都是Trie的常规操作实现。
方法一：链式动态Trie实现
struct TrieNode {
TrieNode * child[26];
bool isEnd;
TrieNode(): isEnd(false) {
for (int i = 0; i < 26; i++) {
child[i] = nullptr;
}
}
};
class WordDictionary {
public:
WordDictionary() {
trie = new TrieNode();
}
void addWord(string word) {
TrieNode* t = trie;
for (auto && tt : word) {
if (t->child[tt - 'a'] == nullptr) {
t->child[tt - 'a'] = new TrieNode;
}
t = t->child[tt - 'a'];
}
t->isEnd = true;
}
bool search(string word) {
return dfs(word, 0, trie);
}
bool dfs(const string & word, int index, TrieNode * node) {
if (index == word.size()) {
return node->isEnd;
}
char ch = word[index];
if (ch >= 'a' && ch <= 'z') {
TrieNode * child = node->child[ch - 'a'];
if (child != nullptr && dfs(word, index + 1, child)) {
return true;
}
} else if (ch == '.') {
for (int i = 0; i < 26; i++) {
TrieNode * child = node->child[i];
if (child != nullptr && dfs(word, index + 1, child)) {
return true;
}
}
}
return false;
}
private:
TrieNode * trie;
};
方法二：二维数组实现静态Trie
#define MAXN 35000
class WordDictionary {
int Trie[MAXN][26];
bool isEnd[MAXN];
int tot;
public:
WordDictionary() {
memset(Trie, 0, sizeof(Trie));
memset(isEnd, 0, sizeof(isEnd));
tot = 0;
}
void addWord(string word) {
int t = 0;
for (int i = 0; i < word.size(); i++) {
char tt = word[i];
if (Trie[t][tt - 'a'] == 0) {
Trie[t][tt - 'a'] = ++tot;
}
t = Trie[t][tt - 'a'];
}
isEnd[t] = true;
}
bool search(string word) {
return dfs(word, 0, 0);
}
bool dfs(const string & word, int index, int to) {
if (index == word.size()) {
return isEnd[to];
}
char ch = word[index];
if (ch >= 'a' && ch <= 'z') {
int q = Trie[to][ch - 'a'];
if (q != 0 && dfs(word, index + 1, q)) {
return true;
}
} else if (ch == '.') {
for (int i = 0; i < 26; i++) {
int q = Trie[to][i];
if (q != 0 && dfs(word, index + 1, q)) {
return true;
}
}
}
return false;
}
};