Python Simple Solution


  • 1

    Since the input set is small and the character set is finite, it is acceptable to enumerate through all possible combinations and see if the new word exists in the dictionary and the time complexity for search is O(k^2) where k is the length of the word.

    Funnily enough, the comment in the skeleton for the search method already hints at using a "trie" but it's not needed to pass the contest.

    - Yangshun

    class MagicDictionary(object):
    
        def __init__(self):
            self.words = None
    
        def buildDict(self, dict):
            self.words = set(dict)
    
        def search(self, word):
            chars = set(word)
            for index, char in enumerate(word):
                for i in range(26):
                    sub = chr(ord('a') + i)
                    if sub == char:
                        continue
                    new_word = word[:index] + sub + word[index + 1:]
                    if new_word in self.words:
                        return True
            return False
    

  • 0
    C
    This post is deleted!

  • 1

    This is not O(k). It's O(k^2) because it's taking C * k at each char in 'word' due to the substring generation. Thus the algorithm will perform C * k operations for k characters == O(k^2)


  • 2

    @Ellest You're right, I missed that out. Have edited the answer to account for that. Thanks for pointing it out (:


Log in to reply
 

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