Problem statement

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

Solution

One approach is to use tries with dfs: let us for each length of word create its own trie. Then let us iterate over all our trie with dfs.

Complexity

Time complexity to create trie is O(s), where s is total length of all words in dictionary. Time complexity to search potentially can be O(26k^2), where k is length of word we are search for. Also it is no more than O(s). Space complexity is O(s).

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_node = 0

class MagicDictionary:
    def __init__(self):
        self.roots = defaultdict(TrieNode)
        
    def buildDict(self, dictionary):
        for word in dictionary:
            root = self.roots[len(word)]
            for symbol in word:
                root = root.children.setdefault(symbol, TrieNode())
            root.end_node = 1
            
    def dfs(self, i, word, changes, pos):
        if changes == 0 and i == len(word) and pos.end_node == 1: 
            return True
        
        for s in pos.children:
            if i < len(word) and (t := changes - (s != word[i])) >= 0:
                if self.dfs(i+1, word, t, pos.children[s]): return True
        return False
            
    def search(self, searchWord):
        return self.dfs(0, searchWord, 1, self.roots[len(searchWord)])

Remark

There is another solution, using generalized neighbors: for each word apple generate *pple, a*ple, ap*le, app*e, appl* and put them to set. Then if we have new word ample, we generate all its neighbors and check if we have some of them in our set. However *pple is neighbor of apple itself, so we need to count how many times we have generalized neighbor in set: if 2 or more, we are fine, if only 1, we check that it is not apple. Time complexity to initialize is $O(\sum\limits_{i}w_i^2)$, where $w_1,\dots, w_k$ are lengths of words in dictionary, time complexity to check new word of length $k$ is $O(k^2)$. Space complexity of initialize is $O(\sum\limits_{i}w_i^2)$, space complexity of check new word of length k is O(k^2)