LeetCode 211 Design Add and Search Words Data Structure

LeetCode

<div>

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

<pre>Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true]

Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True </pre>

Constraints:

• 1 <= word.length <= 500
• word in addWord consists lower-case English letters.
• word in search consist of  '.' or lower-case English letters.
• At most 50000 calls will be made to addWord and search.

</div>

题目大意：

设计一个数据结构支持加单词和查找单词。查找单词支持dot查询，表示配对任意字符

解题思路：

第一时间想到Trie，但难点在如果支持dot。一般Trie实现只支持单一单词查询，但是此题需要搜索所有可能节点。所以要将search加入TrieNode参数且转成DFS

解题步骤：

N/A

注意事项：

1. search加入TrieNode参数且转成DFS
2. 终止条件第二个用TrieNode为空而不是用is_end

Python代码：

class WordDictionary(TestCases):

    def __init__(self):
        self.head = TrieNode()

    def addWord(self, word: str) -> None:
        it = self.head
        for i in range(len(word)):
            it = it.children[word[i]]
        it.is_end = True

    def search(self, word: str) -> bool:
        return self.search_one_node(word, self.head)

    def search_one_node(self, word, trie_node) -> bool:
        if not word and trie_node.is_end:
            return True
        if not word or not trie_node: # remember not trie_node
            return False
        if word[0] == '.':
            for child_node in trie_node.children.values():
                if self.search_one_node(word[1:], child_node):
                    return True
            return False
        if word[0] not in trie_node.children:
            return False
        return self.search_one_node(word[1:], trie_node.children[word[0]])

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.is_end = False

算法分析：

search中不含dot时间复杂度为O(n), 含dot时间复杂度为<code>O(26ⁿ)</code>，空间复杂度O(1), n为搜索单词长度.