Python simple solution-O(N)?


  • 0
    M

    Just refer to the main idea in most of the discussions. Generate a bunch of candidate for the word both in building dict and searching. And need to speical check for the target word cannot be the exact source word in dict (this happens when only matching to one candidate, but when matching to multi candidates, this can be omitted).

    One thing is that, I am not quite sure about the complexity. Just wondering why this time complexity in building is not O(\sum w_i) but O(\sum {w_i}^2), if w_i is length of word for building dictionary? Here when generate the candidates for the word, I need the for-loop and that's one factor of w_i, but how about another one? Other operations just took O(1) time complexity for building or searching in dictionary. Glad to hear from your ideas. Thanks~

    class MagicDictionary(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            
        def buildDict(self, words):
            """
            Build a dictionary through a list of words
            :type dict: List[str]
            :rtype: void
            """
            from collections import defaultdict
            self.d=defaultdict(int)
            for word in words:
                for can in self.iter_can(word):
                    self.d[can]+=1
                self.d[word]=-1
            
        def search(self, word):
            """
            Returns if there is any word in the trie that equals to the given word after modifying exactly one character
            :type word: str
            :rtype: bool
            """
            for can in self.iter_can(word):
                if self.d[can]>1 or (self.d[can]==1 and self.d[word]==0):
                    return True
            return False
            
        def iter_can(self, word):
            n=len(word)
            for i in xrange(n):
                yield word[:i]+"*"+word[i+1:]
    

Log in to reply
 

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