Skip to content

211 Add and Search Word - Data structure design

211. Add and Search Word - Data structure design

题目:

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

难度: Medium

思路:

trie也是树,那么dfs/bfs同样适用。

实际上是照抄208trie的题目再加上dfs

AC代码

class TrieNode(object):
    """docstring for TrieNode"""
    def __init__(self):
        self.childs = dict()
        self.isWord = False

class WordDictionary(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.root = TrieNode()


    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        node = self.root
        for letter in word:
            child = node.childs.get(letter)
            if child is None:
                child = TrieNode()
                node.childs[letter] = child
            node = child
        node.isWord = True


    def search(self, word):
        """
        Returns if the word is in the data structure. A word could
        contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        def dfs(root, word):
            if len(word) == 0:
                return root.isWord
            elif word[0] == '.':
                for node in root.childs:
                    if dfs(root.childs[node], word[1:]):
                        return True
                return False
            else:
                node = root.childs.get(word[0])
                if node is None:
                    return False
                return dfs(node, word[1:])

        return dfs(self.root, word)


回到顶部