LC 0676 [M] Implement Magic Dictionary - ALawliet/algorithms GitHub Wiki

class MagicDictionary(object):
    """
    section complexity
    K - length of search word
    w - average length of each_word in dic
    If counting the time for constructing string
    Time - O(K^2) for search since we create new string every time, which technically takes time K
    Space - O(Sum(w^2))

    If not counting the time for constructing string
    Time - O(K) for search
    Space - for build Sum(w)
    """
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lookup = defaultdict(int)
        # key: the fuzzy word with star e.g. 'apple' => '*pple', 'a*ple', 'ap*le', 'app*e', 'appl*'
        # value: occurrence

    def buildDict(self, dictionary):
        """
        Build a dictionary through a list of words
        :type dict: List[str]
        :rtype: None
        """
        self.words = set(dictionary)
        for word in self.words:
            for candidate in self.candidates(word):
                self.lookup[candidate] += 1
        # print(self.lookup)

    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 candidate in self.candidates(word):
            if self.lookup[candidate] >= 2 or (self.lookup[candidate] == 1 and word not in self.words):
                return True
        return False

    def candidates(self, word):
        for i in range(len(word)):
            yield word[:i] + '*' + word[i+1:] # yield an iterator

class TrieNode:
    def __init__(self, char):
        self.char = char
        self.children = {}
        self.is_end = False
        
class MagicDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = TrieNode("#")

    def add_word(self, word):
        root = self.trie
        
        for char in word:
            if char not in root.children:
                root.children[char] = TrieNode(char)
            
            root = root.children[char]
        
        root.is_end = True
        
    def buildDict(self, dictionary: List[str]) -> None:
        for word in dictionary:
            self.add_word(word)
            
    def search(self, searchWord: str) -> bool:
        return self.dfs(self.trie, searchWord, 1)
    
    def dfs(self, node, word, modifications):
        if modifications < 0: # modifications left to use, -1 means we ran out
            return False
        
        if not word: # no word left to search
            return modifications == 0 and node.is_end # we used just the 1 modification and are at the end of trie
        
        for child in node.children:
            if child == word[0]:
                if self.dfs(node.children[word[0]], word[1:], modifications):
                    return True
            else:
                if self.dfs(node.children[child], word[1:], modifications - 1):
                    return True