Python 168ms-beat-100% solution


  • 23
    B
    class WordDictionary(object):
        def __init__(self):
            self.word_dict = collections.defaultdict(list)
            
    
        def addWord(self, word):
            if word:
                self.word_dict[len(word)].append(word)
    
        def search(self, word):
            if not word:
                return False
            if '.' not in word:
                return word in self.word_dict[len(word)]
            for v in self.word_dict[len(word)]:
                # match xx.xx.x with yyyyyyy
                for i, ch in enumerate(word):
                    if ch != v[i] and ch != '.':
                        break
                else:
                    return True
            return False
    

    The search function could be done in a more pythonic way, but I see that performance has suffered so I just wrote the raw logic by myself.


  • -5
    This post is deleted!

  • 0
    X

    No one say it's a TRIE.


  • 4
    C

    Nice to see that this is actually faster than a trie. Wonder if this is due to the design of test cases.


  • 0
    S

    I also have this question.The "word in word_dict[len(word)]]" seems doing a search in a list? which is O(n) where n is the size of the list. am i correct? Then it will be slow if wordDictionary is huge


  • 0
    K

    It's indeed faster than trie. Can you tell me how the last "else" work ? It's not in the same level with if, but what surprise me is that it does work !!


  • 5
    B

  • 0
    P

    This is actually beautiful.


  • 0

    Good solution!


  • 0
    F

    The search function can be realized in one line (though with some loss of readability):

            return any(all(x == '.' or x == word2[i] for i,x in enumerate(word)) for word2 in self.word_dict[len(word)]) if '.' in word else word in self.word_dict[len(word)]
    

  • 2
    A

    I think this solution won't work very well in the case where there are lots of added strings with the same length.


  • 0

    @adamlhh

    This code runtime beats 90.22% of python submissions. I just check today.
    I think there are only 13 test case for this problem which means it probably can not handle the large test case.


  • 0
    Y

    what is "ch"?


  • 3

    Using set nested in defaultdict is better for access, comparison, and duplicates removal (in contrast if you use list, an identical word may appear in the list multiple times if you add it multiples.).

    self.word_dict = collections.defaultdict(set)
    

  • 0
    O

    Effective but not clever answer


Log in to reply
 

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