添加与搜索单词 - 数据结构设计

难度: Medium

请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。

实现词典类 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 由 '.' 或小写英文字母组成
最多调用 10⁴ 次 addWord 和 search

Submission

运行时间: 660 ms

内存: 0.0 MB

class trienode(object):
    def __init__(self,):
        self.is_word = False
        self.Map = {}
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = trienode()
        
        

    def addWord(self, word: str) -> None:
        curr = self.trie
        for char in word:
            if(char in curr.Map):
                curr = curr.Map[char]
            else:
                curr.Map[char] = trienode()
                curr = curr.Map[char]
        curr.is_word = True 
            

    def search(self, word: str) -> bool:
        return self.search_word(word,self.trie)
        
    def search_word(self,word: str, node: object):
        
        for i in range(len(word)):
            char = word[i]
            if(char not in node.Map):
                for c in node.Map.keys():
                    child = node.Map[c]
                    if(char=="."):
                        if(self.search_word(word[i+1:],child)):
                            return True 
                return False
            else:
                node = node.Map[char]
        return node.is_word
                    


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

Explain

该题解使用字典树（Trie）的数据结构来解决问题。在添加单词时，将单词的每个字符作为字典树的节点插入。在搜索单词时，从字典树的根节点开始，逐个字符进行匹配。如果遇到 '.'，则对当前节点的所有子节点进行递归搜索。如果搜索到字典树的叶子节点，且该节点标记为单词结尾，则说明找到了匹配的单词。

时间复杂度: 添加单词：O(L)，搜索单词：O(M)

空间复杂度: O(N)

class trienode(object):
    def __init__(self,):
        self.is_word = False
        self.Map = {}

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = trienode()
        
    def addWord(self, word: str) -> None:
        """
        添加单词到字典树中
        """
        curr = self.trie
        for char in word:
            if(char in curr.Map):
                curr = curr.Map[char]
            else:
                curr.Map[char] = trienode()
                curr = curr.Map[char]
        curr.is_word = True 
            
    def search(self, word: str) -> bool:
        """
        在字典树中搜索单词
        """
        return self.search_word(word,self.trie)
        
    def search_word(self,word: str, node: object):
        """
        递归搜索单词
        """
        for i in range(len(word)):
            char = word[i]
            if(char not in node.Map):
                for c in node.Map.keys():
                    child = node.Map[c]
                    if(char=="."):
                        if(self.search_word(word[i+1:],child)):
                            return True 
                return False
            else:
                node = node.Map[char]
        return node.is_word

Explore

在`search`函数中，'.'字符被设计为一个通配符，它可以匹配任意一个字符。因此，当遇到'.'时，必须考虑字典树中当前节点下的所有可能的子节点。这是因为任何一个子节点都有可能是目标单词路径的一部分。如果只选择特定的子节点进行搜索，将无法保证完全匹配所有可能的单词，特别是在不知道下一个字符应该是什么的情况下。

`is_word`属性在字典树的节点中用于标识该节点是否代表单词的结束。当添加一个单词到字典树时，该单词的最后一个字符对应的节点会将`is_word`设置为真。在搜索过程中，即使成功地匹配到了单词的最后一个字符，如果该字符对应的节点的`is_word`属性不为真，则表明该路径虽然存在，但不代表一个完整的单词。例如，如果单词'good'在字典树中，但是搜索'goo'，虽然路径存在，但'goo'的结尾节点`is_word`为假，因此不会返回找到单词。

在添加单词到字典树时，重复字符被正常处理，按照单词的顺序逐个添加到字典树中。例如，首先添加'good'，将会创建路径g -> o -> o -> d，节点d的`is_word`被设置为真。当添加'goody'时，从根节点开始，g和o已存在，继续沿用现有路径。到达d后，添加一个新的子节点y，将y的`is_word`设置为真。这样，字典树能够共享前缀，节省空间，同时能够区分不同的单词。

确实，如果输入单词非常长或字典树结构特别深，递归调用可能导致栈溢出。为防止这种情况，可以考虑使用迭代而非递归进行搜索。迭代方法可以使用栈或队列显式管理节点而不依赖于函数调用栈，从而避免栈溢出的风险。此外，还可以设置递归深度限制或优化字典树的结构，比如通过压缩路径或合并冗余节点来减少树的深度。