Leetcode 676 Solution

This article provides solution to leetcode question 676 (implement-magic-dictionary)
Categories:
Tags:
Access this page by simply typing in "lcs 676" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/implement-magic-dictionary

Solution

class MagicDictionary:



    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.m = collections.defaultdict(set)



    def buildDict(self, dict: List[str]) -> None:
        """
        Build a dictionary through a list of words
        """
        for word in dict:
            for i in range(len(word)):
                self.m[word[:i] + '*' + word[(i + 1):]].add(word[i])



    def search(self, word: str) -> bool:
        """
        Returns if there is any word in the trie that equals to the given word after modifying exactly one character
        """
        for i in range(len(word)):
            key = word[:i] + '*' + word[(i + 1):]
            if key in self.m and {word[i]} != self.m[key]:
                return True
        return False



# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dict)
# param_2 = obj.search(word)