211. 添加与搜索单词 - 数据结构设计 [medium]

211. 添加与搜索单词 - 数据结构设计 [medium]

https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/

设计一个支持以下两种操作的数据结构：

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 组成的。

通过次数13,116 | 提交次数28,854

Second Try

2020-07-22

相比first try,根本没必要在轮询的时候到下一轮才判断是否存在，直接在最后一个元素key对应的node里设置is_end就行了。

class Node(dict):
    def __init__(self):
        self.is_end = False 

class WordDictionary:
    """
    ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
    [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
    """
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.node = Node()

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        node = self.node 
        for c in word:
            if c not in node:
                node[c] = Node()
            node = node[c]
        node.is_end = True 
        # print(self.node)  # 打印出来发现is_end信息并不会被当作keys
                

    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.
        """

        def check(word, node):
            # bug写法，在word为空的时候，要判断的是上一层的node的信息，而不是下一层的node的is_end信息
            if len(word) == 0:
                return node.is_end 
            for i in range(len(word)):
                if word[i] == ".":
                    for knode in node.values():
                        if isinstance(knode, Node): # 排除is_end和None的存在
                            if check(word[i+1:], knode):
                                return True 
                    return False 
                if word[i] not in node:
                    return False 
                node = node[word[i]]
            return node.is_end

        return check(word, self.node)
        

• 执行用时：396 ms, 在所有 Python3 提交中击败了32.62%的用户
• 内存消耗：27.7 MB, 在所有 Python3 提交中击败了100.00%的用户

First Try

2020-07-22

又有add word又有search，还都是小写字母，明显就是一颗trie树。

相比208题，换了一种trie树的基础结构，用的是字典而不是列表，应该能节省一些空间。 其次对dict进行基层，可以发现keys()其实并不会包括作为属性的self.is_end，因此直接进行遍历并无影响。

search对通配符的处理，明显就是要用递归，不过还是先假设不存在通配符写完一版，然后加上通配符进行改造修改为递归版本，思路就清晰了许多。如果一开始就要写出递归，容易出bug。

有一个容易出bug的地方，在判断末尾的时候，循环得到的其实是下一个层次的node，但是判断is_end其实需要的是上一层node的信息。比如search递归到word为空的时候，传递的node参数是下一层次的，没法判断，只能在调用递归前进行判断处理。 归根到底，判断一个char是否存在某一层的node里面，是通过将该char设置为key，将空白node设置为value来实现的，每次判断存在后返回的其实是下一个空白的node.

anyway，写起trie树已经轻车熟路了。

class Node(dict):
    def __init__(self):
        # node.keys()并不会包含is_end
        self.is_end = False 

class WordDictionary:
    """
    ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
    [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
    """
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.node = Node()

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        node = self.node 
        for c in word:
            last_node = node # 最后的有效节点
            if c not in node:
                node[c] = Node()
            node = node[c]
        last_node.is_end = True 
        # print(self.node)  # 打印出来发现is_end信息并不会被当作keys
                

    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.
        """

        def check(word, node):
            # bug写法，在word为空的时候，要判断的是上一层的node的信息，而不是下一层的node的is_end信息
            # if len(word) == 0:
            #     return node.is_end 
            for i in range(len(word)):
                if word[i] == ".":
                    for knode in node.values():
                        if isinstance(knode, Node): # 排除is_end和None的存在
                            if i == len(word) - 1:
                                return node.is_end # 直接在此处进行拦截，不然传递下去的是下一层的knode，而不是当前的node
                            if check(word[i+1:], knode):
                                return True 
                    return False 
                last_node = node 
                if word[i] not in node:
                    return False 
                node = node[word[i]]
            return last_node.is_end

        return check(word, self.node)
        




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

• 执行用时：232 ms, 在所有 Python3 提交中击败了78.83%的用户
• 内存消耗：27.7 MB, 在所有 Python3 提交中击败了100.00%的用户