欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

211. Add and Search Word - Data structure design(难啊)

程序员文章站 2022-05-18 10:03:14
...

题目

211. Add and Search Word - Data structure design(难啊)
一个简单的添加单词,返回查找是否存在的数据结构。

我的代码(超时)

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.words=set()
        

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        self.words.add(word)

    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.
        """
        for s in self.words:
            if re.match(word+'$', s, flags=0):
                return True
        return False
        


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

讨论区代码(效率中等/但方法很神奇)

初始版本:

class WordDictionary:

    def __init__(self):
        self.root = {}
    
    def addWord(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[None] = None
   # 一个容易理解的search
    def search(self, word):
        def find(word, node):
            if not word:
                return None in node
            char, word = word[0], word[1:]
            if char != '.':
                return char in node and find(word, node[char])
            return any(find(word, kid) for kid in node.values() if kid)

两种search:

    def search(self, word):
        nodes = [self.root]
        for char in word:
            nodes = [kid
                     for node in nodes
                     for key, kid in node.items()
                     if char in (key, '.') and kid]
        return any(None in node for node in nodes)
And one that's a bit longer but faster:

    def search(self, word):
        nodes = [self.root]
        for char in word:
            nodes = [kid for node in nodes for kid in
                     ([node[char]] if char in node else
                      filter(None, node.values()) if char == '.' else [])]
        return any(None in node for node in nodes)

最后的简洁版本:

class WordDictionary:

    def __init__(self):
        self.root = {}
    # 添加了一个树状的字典
    def addWord(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node['$'] = None
        print(self.root)
   	# 逐层查询结果 
    def search(self, word):
        nodes = [self.root]
        for char in word + '$':
            nodes = [kid for node in nodes for kid in
                     ([node[char]] if char in node else
                      filter(None, node.values()) if char == '.' else [])]
        return bool(nodes)

高效代码

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = collections.defaultdict(list)
    
    def addWord(self, word: 'str') -> 'None':
        """
        Adds a word into the data structure.
        """
        # 根据长度来分类单词
        if word:
            self.dic[len(word)].append(word)
    
    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.
        """
        # 如果没有. 符号就简单了
        if "." not in word:
            return word in self.dic[len(word)]
        
        # 如果有.就需要逐个字符判断。
        for word2 in self.dic[len(word)]:
            for i, c1 in enumerate(word):
                if c1 != "." and word2[i] != c1:
                    break
            else:
                return True
        return False
相关标签: leetcode