1. 题目来源
- 分类：字典树
- Leetcode211:单词搜索I
2. 题目描述
设计一个支持以下两种操作的数据结构：
void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
示例:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
说明:你可以假设所有单词都是由小写字母 a-z 组成的。
3. 解题思路
根据Trie Tree(字典树/前缀树/单词查找树)对Trie基本结构的描述，进行插入编写即可，此题中的查找涉及正则表达式字符的查找，所以遇到字符为‘.’需要递归匹配。
例如：插入字符串：bcd, dad, ead, ecd得到字典树如下
构建字典树
如查找字符串'.ad', 当遇到字符'.'时，则需要在此层遍历以存在字符开始存在的所有的路径中是否存在匹配路径。
具体查找如下：
- 第一次以b匹配'.', 之后以b为父节点匹配剩余字符a，b->c路径不匹配，则继续匹配b->a，但a.isEnd=True, 返回false；
- 第一次以d匹配'.', 之后以d为父节点匹配剩余字符a，b->a路径, 继续匹配剩余字符d, b->a->d匹配，无剩余字符且d.isEnd = True 返回 true 匹配成功。
若上述步骤仍不匹配，则继续匹配以e开始匹配的所有路径中是否存在所需匹配路径。
4. 编程实现
Python
class TrieNode:
def __init__(self):
self.next = [None for i in range(26)]
self.isEnd = False
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def addWord(self, word: str) -> None:
"""
Adds a word into the data structure.
"""
node = self.root
for i in range(len(word)):
if node.next[ord(word[i]) - ord('a')] == None:
node.next[ord(word[i]) - ord('a')] = TrieNode()
node = node.next[ord(word[i]) - ord('a')]
node.isEnd = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
"""
return self.match(self.root, word, 0)
def match(self, node, word, start):
if start == len(word):
return node.isEnd
if word[start] == '.':
for i in range(26):
if node.next[i] and self.match(node.next[i], word, start + 1):
return True
return False
else:
if node.next[ord(word[start]) - ord('a')] == None:
return False
return self.match(node.next[ord(word[start]) - ord('a')], word, start + 1)
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
