How hard is LeetCode 676. Implement Magic Dictionary?

LeetCode 676. Implement Magic Dictionary is rated Medium on LeetCode.

What is the time complexity of LeetCode 676. Implement Magic Dictionary?

The Python solution on this page runs in O(n \times l + q \times l \times |\Sigma|).

What is the space complexity of LeetCode 676. Implement Magic Dictionary?

The Python solution on this page uses O(n \times l), where n and l are the number of words in the dictionary and the average length of the words, respectively, and q is the number of words searched auxiliary space.

What topics does LeetCode 676. Implement Magic Dictionary cover?

LeetCode 676. Implement Magic Dictionary is tagged Depth-First Search, Design, Trie, Hash Table and String on LeetCode.

Implement Magic Dictionary — LeetCode 676 Python Solution

MediumDepth-First SearchDesignTrieHash TableString

Problem: #676
Pattern: Trie
Reading time: 8 min
Source: leetcode.com

The problem

Design a data structure that is initialized with a list of different words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.

Example

Input: ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
Output: [null, null, false, true, false, false]
Explanation: MagicDictionary magicDictionary = new MagicDictionary();

Python solution

Python

class Trie:
    __slots__ = "children", "is_end"

    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26
        self.is_end = False

    def insert(self, w: str) -> None:
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, w: str) -> bool:
        def dfs(i: int, node: Optional[Trie], diff: int) -> bool:
            if i == len(w):
                return diff == 1 and node.is_end
            j = ord(w[i]) - ord("a")
            if node.children[j] and dfs(i + 1, node.children[j], diff):
                return True
            return diff == 0 and any(
                node.children[k] and dfs(i + 1, node.children[k], 1)
                for k in range(26)
                if k != j
            )

        return dfs(0, self, 0)


class MagicDictionary:
    def __init__(self):
        self.trie = Trie()

    def buildDict(self, dictionary: List[str]) -> None:
        for w in dictionary:
            self.trie.insert(w)

    def search(self, searchWord: str) -> bool:
        return self.trie.search(searchWord)


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

Complexity

Measure	Complexity
Time	O(n \times l + q \times l \times \|\Sigma\|)
Space	O(n \times l), where n and l are the number of words in the dictionary and the average length of the words, respectively, and q is the number of words searched auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 676. Implement Magic Dictionary is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 676. Implement Magic Dictionary?: LeetCode 676. Implement Magic Dictionary is rated Medium on LeetCode.
What is the time complexity of LeetCode 676. Implement Magic Dictionary?: The Python solution on this page runs in O(n \times l + q \times l \times |\Sigma|).
What is the space complexity of LeetCode 676. Implement Magic Dictionary?: The Python solution on this page uses O(n \times l), where n and l are the number of words in the dictionary and the average length of the words, respectively, and q is the number of words searched auxiliary space.
What topics does LeetCode 676. Implement Magic Dictionary cover?: LeetCode 676. Implement Magic Dictionary is tagged Depth-First Search, Design, Trie, Hash Table and String on LeetCode.