676. Implement Magic Dictionary

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

Implement Magic Dictionary - LeetCode

check whether the word made by flipping one charater of given word exists in the dictionary

 

500ms (Terrible solution)

class TreeNode:
    
    def __init__(self, char, is_end=False):
        self.char = char
        self.children = dict() # key: char, val: TreeNode
        self.is_end = is_end
    
    def __repr__(self):
        return 'char: {}, next: {}, is_end: {}'.format(self.char, self.next, self.is_end)
        
        
class MagicDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TreeNode(None)

    def buildDict(self, dictionary: List[str]) -> None:
        
        for word in dictionary:
            root = self.root
            for i, c in enumerate(word):
                is_end = (i == len(word)-1)
                if c not in root.children:
                    root.children[c] = TreeNode(c)
                root = root.children[c]
                root.is_end |= is_end
        
    def search(self, searchWord: str) -> bool:
        
        def dfs(root: TreeNode, subWord: str, fail: int) -> bool:
            if len(subWord) == 0:
                return fail == 1 and root.is_end
            if fail > 1:
                return False
            
            cur_char = subWord[0]
            res = False
            for child_key, node in root.children.items():
                if cur_char == child_key:
                    res |= dfs(node, subWord[1:], fail)
                else:
                    res |= dfs(node, subWord[1:], fail+1)
            
            return res
        
        return dfs(self.root, searchWord, 0)
    

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

 

no need to implement trie

focus on the length of words

 

100ms

from collections import defaultdict, Counter
class MagicDictionary:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = defaultdict(list)

    def buildDict(self, words: List[str]) -> None:
        """
        Build a dictionary through a list of words
        """
        for word in words:
            self.trie[len(word)] += [word]
        
    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
        """
        n = len(word)
        
        for w in self.trie[n]:
            cur = list(word)
            diff = 0
            
            for k, char in enumerate(w):
                if diff > 1:
                    break
                if char == cur[k]:
                    continue
                diff += 1
            if diff == 1:
                return True
                
        return False