Leetcode211. 添加与搜索单词 - 数据结构设计
题目描述：
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。
示例：
输入：
[“WordDictionary”,“addWord”,“addWord”,“addWord”,“search”,“search”,“search”,“search”]
[[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b…”]]
输出：
[null,null,null,null,false,true,true,true]
解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord(“bad”);
wordDictionary.addWord(“dad”);
wordDictionary.addWord(“mad”);
wordDictionary.search(“pad”); // 返回 False
wordDictionary.search(“bad”); // 返回 True
wordDictionary.search(“.ad”); // 返回 True
wordDictionary.search(“b…”); // 返回 True
提示：
1 <= word.length <= 25
addWord 中的 word 由小写英文字母组成
search 中的 word 由 ‘.’ 或小写英文字母组成
最多调用 104 次 addWord 和 search
解题思路
根据题意，WordDictionary\texttt{WordDictionary}WordDictionary 类需要支持添加单词和搜索单词的操作，可以使用字典树实现。
对于添加单词，将单词添加到字典树中即可。
对于搜索单词，从字典树的根结点开始搜索。由于待搜索的单词可能包含点号，因此在搜索过程中需要考虑点号的处理。对于当前字符是字母和点号的情况，分别按照如下方式处理：
如果当前字符是字母，则判断当前字符对应的子结点是否存在，如果子结点存在则移动到子结点，继续搜索下一个字符，如果子结点不存在则说明单词不存在，返回 false\text{false}false；
如果当前字符是点号，由于点号可以表示任何字母，因此需要对当前结点的所有非空子结点继续搜索下一个字符。
重复上述步骤，直到返回 false\text{false}false 或搜索完给定单词的最后一个字符。
如果搜索完给定的单词的最后一个字符，则当搜索到的最后一个结点的 isEnd\textit{isEnd}isEnd 为 true\text{true}true 时，给定的单词存在。
特别地，当搜索到点号时，只要存在一个非空子结点可以搜索到给定的单词，即返回 true\text{true}true。
代码实现
public class WordDictionary {public class TrieNode {public TrieNode[] children = new TrieNode[26];public String item = "";}private TrieNode root = new TrieNode();public void addWord(String word) {TrieNode node = root;for (char c : word.toCharArray()) {if (node.children[c - 'a'] == null) {node.children[c - 'a'] = new TrieNode();}node = node.children[c - 'a'];}node.item = word;}public boolean search(String word) {return match(word.toCharArray(), 0, root);}private boolean match(char[] chs, int k, TrieNode node) {if (k == chs.length) return !node.item.equals("");if (chs[k] != '.') {return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);} else {for (int i = 0; i < node.children.length; i++) {if (node.children[i] != null) {if (match(chs, k + 1, node.children[i])) {return true;}}}}return false;}
}