inverted index in python beat 99.69%, straightforward


  • 0
    F
    class MagicDictionary(object):
        def __init__(self):
            from collections import defaultdict
            self.inverted_index = defaultdict(list)
    
        def buildDict(self, dict):
            for word in dict:
                self.inverted_index[len(word)].append(word)
    
        def search(self, word):
            candidates = self.inverted_index[len(word)]
            for candidate in candidates:
                if self.validate(word, candidate):
                    return True
            return False
    
        def validate(self, s1, s2):
            diff = 0
            for c1, c2 in zip(s1, s2):
                if c1 != c2:
                    diff += 1
                if diff > 1:
                    return False
            return diff == 1

Log in to reply
 

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