Accepted concise python solution, based on Trie

  • 1
    class WordDictionary(object):
        def __init__(self):
            self.chars = {}  #each char is the key and each key has a dict as its value
        def addWord(self, word):
            curr = self.chars
            for c in word:
                if c not in curr:
                    curr[c] = {}
                curr = curr[c]
            curr['#'] = {}  #indicate the end of a word
        def search(self, word):
            return self.search_dfs(word, self.chars)
        def search_dfs(self, word, curr):
            if len(word)==0:
                return '#' in curr
            c = word[0]
            if c == '.':
                for char in curr:
                    if self.search_dfs(word[1:], curr[char]):
                        return True
                return False
            # now c is a-z
            if c in curr:
                return self.search_dfs(word[1:], curr[c])
            return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.