676 Implement Magic Dictionary

Implement a magic directory withbuildDict, andsearchmethods.

For the methodbuildDict, you'll be given a list of non-repetitive words to build a dictionary.

For the methodsearch, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

Note:

1. You may assume that all the inputs are consist of lowercase letters a-z.

2. For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.

3. Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

The Idea: Generate a unique hash for every word that does not include the character from the word at every position in that word. For example, "hello" -> {"ello":[[0, 'h']], "hllo":[[1, 'e']], "helo":[[2, 'l'],[3, 'l']], "hell":[[4, 'o']]}. Now for a search, do the same thing, and try to identify that word in the dictionary that does not include the character at that position of the word. If the subsequence exists in the dictionary, and it happened to be at the same index where the character that was removed, and the characters are different that means there exists a word in the dictionary that is different by 1 character at that exact position. There is one small flaw in this design. Consider the words hello, and hallo. If I where to search for the word hello, this solution would return true. This is because halloreplaced the occurrence of e in hllo in the dictionary. To fix this problem, when need to identify when there are two identical subsequence hashes with the same index. Lets think about this case. When we search for that subsequence with a query, it doesnt matter whether or not to take a or e. If it happens to be a such as in hallo, then e will be the functionally different character, and if the query happens to be e such as in hello, then a in hallo will serve as the difference-of-one-string. Because we know that every string is going to be lowercase a-z, we can to assign $ as the special character to signal this case. However, we are still not done. Consider the case hello, which will contain two occurrences of helo in the dictionary, since two l's occur one after another. To fix these cases, replace the character removed in the hash with another special character to make sure that it is unique again. I used ..

Complexity: O(n*m) build dict, and O(m) time for search where n is the number of words in the dictionary and m is the average length of each word.

class MagicDictionary:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = {}

    def buildDict(self, dict):
        """
        Build a dictionary through a list of words
        :type dict: List[str]
        :rtype: void
        """
        for word in dict:
            for i, char in enumerate(word):
                partial_word = word[:i] + '.' +  word[i+1:]
                if partial_word not in self.d:
                    self.d[partial_word] = (i, char)
                else:
                    self.d[partial_word] = (i, '$')

    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 i, char in enumerate(word):
            partial_word = word[:i] + '.' + word[i+1:]
            if partial_word in self.d and \
                            self.d[partial_word][0] == i and \
                            self.d[partial_word][1] != char:
                return True
        return False


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