Design Add and Search Words Data Structure
构建一个支持两种操作的单词字典。addWord w 用于存储单词 w。search p 用于判断是否存在某个已存储的单词与模式 p 匹配：长度相同，并且在每个位置，模式中的字符都与单词中的字母相同，或者是一个点 .，表示任意一个字母。
操作 i 是对单词或模式 words[i] 执行的 ops[i]。按顺序在空字典上执行这些操作，并为每个操作返回一个字符串：对于 addWord，返回 "null"；对于 search，返回 "true" 或 "false"。
函数
- opsstring-array
- 按照运行顺序排列的操作
- wordsstring-array
- 每次操作添加一个单词或搜索一个模式
- 返回值string-array
- 每个操作对应一个答案，作为文本
约束条件
1 ≤ ops.length ≤ 2500words.length == ops.length- 每个
ops[i]都是addWord或search。 1 ≤ words[i].length ≤ 20- 要添加的单词只包含小写英文字母。
- 要搜索的模式由小写英文字母组成，且最多包含 3 个点。
示例
- 输入
- ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
- 输出
- ["null", "null", "true", "false", "false", "true"]
- 解释
r.se可以匹配这两个单词：点号对应rose中的 o 和rise中的 i。点号不能代表缺失的字母，所以ros和rose.都无法匹配。..s.可以匹配，因为这两个单词的第三个字母都是 s。
- 输入
- ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
- 输出
- ["false", "null", "true", "true", "false"]
- 解释
- 字典一开始是空的，所以
...找不到任何内容。添加sky后，...和s.y都能匹配它，而sk太短了。
- 输入
- ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
- 输出
- ["null", "null", "true", "false", "true"]
- 解释
ma..o中的第一个点可以是maple中的 p，也可以是mango中的 n；maple以 e 结尾，但mango符合条件。没有单词以 y 结尾，所以m...y不匹配，而m.p.e与maple匹配。
进阶
如果模式还可以包含 *，表示任意长度的字母序列（包括空序列），你会如何扩展 search？
提示
逐个打开提示，每个都会多透露一点。
没有点号时，存储这些单词的哈希集合只需查找一次，就能回答每次搜索。点号会打破这一点：
c.t可能是cat、cot或cut。哪种数据结构能让你逐个字母地查找一个单词，并查看接下来可能出现的每个字母？把单词存储在字典树中，并在每个单词结尾所在的节点上设置标记。模式中的字母沿着一条子节点链接前进。点可以代表任意字母，因此需要尝试当前节点的每个子节点；如果某个分支走到尽头，就回退。
编写递归函数
match(node, i)。到达模式末尾时，根据节点的结束标志返回结果。遇到字母时，沿着对应的子节点继续查找；如果该子节点不存在，则失败。遇到点时，只要某个子节点的match(child, i+1)返回成功，就立即返回 true；如果没有任何子节点成功，则返回 false。
题解
点号表示搜索无法指定它要找的字母：ma..o代表 676 个可能的单词，只有已存储的单词才重要。在字典树中，开头相同的单词会共用一条路径。模式中的字母沿着一条链接前进，点号只会扩展到实际存在的子节点，深度优先搜索会从走不通的分支回退。
将模式与每个存储的单词进行比较
思路
把添加的单词保存在列表中，并逐个检查它们是否符合模式：长度相同，而且每个位置上的字母要么是点，要么与模式中相同位置的字母相同。这就是匹配的定义。对保存的每个单词都进行检查，才能得到正确答案。
每次搜索都要遍历整个列表。对于最多有 L 个字母的 n 个单词，时间复杂度为 O(n·L)，即使模式中没有点也一样。添加 1,250 个单词后再搜索 1,250 次，需要检查 1,250 × 1,250 = 1,562,500 个单词。
算法
- 将添加的单词保存在列表中。对于
addWord w，追加w，并记录"null"。 - 对于
search p，将p与每个长度相同的单词逐个按位置比较，让点号匹配任意字母。 - 首次匹配时记录
"true"，如果没有匹配项，则记录"false"。
def matches(pattern, word):
# Same length, and every position holds a dot or the same letter.
if len(pattern) != len(word):
return False
for p, w in zip(pattern, word):
if p != "." and p != w:
return False
return True
def wordDictionaryOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "addWord":
stored.append(word)
result.append("null")
else:
found = any(matches(word, s) for s in stored)
result.append("true" if found else "false")
return result使用深度优先搜索遍历点分隔的 Trie
思路
把单词存入字典树：rose 和 rise 共用 r 节点，然后分成 o 和 i。结束标记表示存储的单词在哪个节点结束。字母组成的模式就是沿着字典树向下的一条路径。点可以代表任意字母，所以遇到点时，尝试每个已有的子节点，只要其中一个能匹配，就立即返回 true。
对于 ma..o，ma 对应的节点有 p 和 n 两个子节点。沿着 p 走，第二个点会到达 l，但它没有 o 子节点，所以搜索会回退并尝试 n：然后是 g，再然后是 o，此时结束标记表示单词 mango 到此结束。
匹配必须在带有结束标记的节点上用完整个模式，这样就能确定长度：ros 会停在没有结束标记的节点上，而 rose. 会因链接用尽而无法匹配。一个点最多展开 26 个分支，所以有 d 个点的模式最多会访问 26^d · L 个节点，而不含点的模式的开销为 O(L)。
算法
- 每个节点都有子链接和一个结束标记，初始为关闭状态。
- 对于
addWord w：从根节点开始，沿着w遍历，创建缺失的节点，并在遍历停止的位置设置结束标记。 match(node, i)：如果i等于模式的长度，就返回该节点的结束标记。- 如果
p[i]是字母，那么如果它的子节点不存在，就返回 false，否则返回match(child, i+1)。如果它是点号，那么只要任意一个现有子节点的match(child, i+1)成功，就返回 true，否则返回 false。 - 每次搜索都记录
match(root, 0)，每次添加都记录"null"。
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def add_word(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, pattern):
return self._match(self.root, pattern, 0)
def _match(self, node, pattern, i):
# Can the path below node spell pattern[i:] and end on a stored word?
if i == len(pattern):
return node.is_end
ch = pattern[i]
if ch == ".":
# A dot stands for any letter: try each child until one works.
for child in node.children.values():
if self._match(child, pattern, i + 1):
return True
return False
child = node.children.get(ch)
return child is not None and self._match(child, pattern, i + 1)
def wordDictionaryOps(ops, words):
dictionary = WordDictionary()
result = []
for op, word in zip(ops, words):
if op == "addWord":
dictionary.add_word(word)
result.append("null")
else:
result.append("true" if dictionary.search(word) else "false")
return result
易错点和边界情况
- 让第一个子节点决定点号的匹配结果。在
ma..o中，p 分支匹配失败，n 分支匹配成功，所以先尝试 p 分支并返回第一个子节点结果的代码会返回 false。只有所有子节点都匹配失败后，才返回 false。 - 模式在任意节点结束时都返回 true。添加
rose后，ros会到达一个节点，但没有单词在此结束。请检查结束标记。 - 让点号匹配缺失的字母。
card.能匹配cards，但不能匹配card。 - 把点号当作字母处理。用
'.' - 'a'索引一个有 26 个槽位的数组会访问数组范围之外的位置，所以要先检查点号。
常见问题3
Add 和 Search Words 的时间复杂度是多少？
添加一个长度为 L 的单词需要 O(L)，不含点的搜索也是如此，无论存储了多少个单词。最坏情况下，包含 d 个点的搜索需要 O(26^d · L)。对于已添加的 T 个字母，内存需要 O(T) 个节点。
你能用哈希集合而不是字典树来解决这个问题吗？
可以，但各有取舍。集合可以通过一次查找匹配不含点的模式。对于点，你可以扫描所有已存储的、长度相同的单词，复杂度为 O(n·L)；也可以用全部 26 个字母替换每个点，并查找每种结果。三个点就需要查找 17,576 次。
Trie 搜索应该使用递归还是迭代？
两种方式都可以。递归每遇到一个模式字母就深入一层，这里最多 20 层，因此调用栈不会很大。迭代版本会保存由（节点、位置）组成的栈，并在遇到点号时将每个子节点压入栈中。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def wordDictionaryOps(ops, words):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
预期输出
["null", "null", "true", "false", "false", "true"]