algoadvance

Leetcode Problem 676: Implement a Magic Dictionary

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.

Implement the MagicDictionary class:

Clarifying Questions

  1. Does the dictionary contain only lowercase English letters?
    • Yes, according to the problem statement.
  2. Can words in the dictionary have varying lengths?
    • Yes, the words in the dictionary can have different lengths.
  3. Should the search function consider words of different lengths as potential matches?
    • No, only words of the same length should be considered for matching by changing exactly one character.

Strategy

  1. Store the Dictionary Words: Create a data structure to store the dictionary words for efficient searching.
  2. Search for Matches with One Character Difference: To determine if there is a word in the dictionary that can be formed by changing exactly one character, traverse through each character of the search word and check if changing it to any other character (or dictionary word) results in a match.

Code Implementation

class MagicDictionary:

    def __init__(self):
        self.dictionary = {}

    def buildDict(self, dictionary: List[str]) -> None:
        self.dictionary = {}
        for word in dictionary:
            n = len(word)
            if n in self.dictionary:
                self.dictionary[n].append(word)
            else:
                self.dictionary[n] = [word]

    def search(self, searchWord: str) -> bool:
        n = len(searchWord)
        if n not in self.dictionary:
            return False
        for word in self.dictionary[n]:
            count_differences = 0
            for wc, swc in zip(word, searchWord):
                if wc != swc:
                    count_differences += 1
                if count_differences > 1:
                    break
            if count_differences == 1:
                return True
        return False

Strategy

  1. Initialization & Structure:
    • Use a dictionary to store lists of words grouped by their lengths, allowing efficient lookup based on the length of the search word.
  2. Building the Dictionary:
    • During the buildDict method, populate the dictionary where keys are word lengths, and values are lists of words of that length.
  3. Searching with One Character Difference:
    • For a given searchWord, retrieve the list of potential matching words from the dictionary based on its length.
    • Compare each character of the searchWord with words from the dictionary.
    • Count the number of differing characters. If exactly one character differs, return True.
    • If no such word is found, return False.

Time Complexity

  1. buildDict(dictionary) Method:
    • Time complexity: (O(N)) where (N) is the total number of characters in all the words in the dictionary.
  2. search(searchWord) Method:
    • Time complexity:
      • Average case: (O(M \cdot L)) where (M) is the number of dictionary words of the same length as searchWord and (L) is the length of the searchWord.
      • Worst case: (O(K \cdot L)) where (K) is the total number of words in the dictionary.

These operations ensure the implementation is efficient while adhering to the problem constraints.

Try our interview co-pilot at AlgoAdvance.com