We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Implement Magic Dictionary

Difficulty: Medium

Problem Description

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.

Key Insights

  • We need to maintain a collection of distinct words for comparison.
  • The goal is to check if a given word can match any word in the collection by changing exactly one character.
  • This problem can be approached using a hash table or by comparing strings directly.

Space and Time Complexity

Time Complexity: O(N * M) where N is the number of words in the dictionary and M is the length of the longest word.
Space Complexity: O(N) for storing the words in the dictionary.

Solution

To solve the problem, we can use a hash table (or a set) to store the words from the dictionary for quick look-up. When searching for a word, we will iterate through each character in the word and try replacing it with every possible lowercase letter from 'a' to 'z'. For each modified word, we will check if it exists in our dictionary. If we find such a word, we return true; otherwise, we return false.

Code Solutions

class MagicDictionary:

    def __init__(self):
        # Initialize a set to store the words
        self.words = set()

    def buildDict(self, dictionary: List[str]) -> None:
        # Add all words from the dictionary to the set
        self.words = set(dictionary)

    def search(self, searchWord: str) -> bool:
        # Check each character of the searchWord
        for i in range(len(searchWord)):
            # Try replacing the character at position i with every letter from a to z
            for c in 'abcdefghijklmnopqrstuvwxyz':
                # Skip if the character is the same
                if c == searchWord[i]:
                    continue
                # Create a new modified word
                modifiedWord = searchWord[:i] + c + searchWord[i+1:]
                # Check if the modified word exists in the dictionary
                if modifiedWord in self.words:
                    return True
        return False
← Back to All Questions