LC676 - Implement Magic Dictionary

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.
Implement the MagicDictionary class:
MagicDictionary() Initializes the object.
void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.
bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

Example 1:
Input
[“MagicDictionary”, “buildDict”, “search”, “search”, “search”, “search”]
[[], [[“hello”, “leetcode”]], [“hello”], [“hhllo”], [“hell”], [“leetcoded”]]
Output
[null, null, false, true, false, false]
Explanation
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict([“hello”, “leetcode”]);
magicDictionary.search(“hello”); // return False
magicDictionary.search(“hhllo”); // We can change the second ‘h’ to ‘e’ to match “hello” so we return True
magicDictionary.search(“hell”); // return False
magicDictionary.search(“leetcoded”); // return False

Constraints:
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] consists of only lower-case English letters.
All the strings in dictionary are distinct.
1 <= searchWord.length <= 100
searchWord consists of only lower-case English letters.
buildDict will be called only once before search.
At most 100 calls will be made to search.

Solution

• All strings in the buildDict(String[] dictionary) method are stored in the hash set
• Traverse all elements in the set, use double pointers (l, r) and a variable (diff) to determine how many elements in the two strings are different, if diff == 1, return True directly, if all elements in the set are compared Returns False if it has not returned True

  class MagicDictionary:
  
      def __init__(self):
          self.dict = set()
  
      def buildDict(self, dictionary: List[str]) -> None:
          for word in dictionary:
              self.dict.add(word)
  
      def search(self, searchWord: str) -> bool:
          for item in self.dict:
              if len(item) != len(searchWord) or item == searchWord:
                  continue
              diff = 0
              for i in range(len(item)):
                  if item[i] != searchWord[i]:
                      diff+=1
                  if diff >1:
                      break
              if diff == 1:
                  return True
          return False
  
  # Your MagicDictionary object will be instantiated and called as such:
  # obj = MagicDictionary()
  # obj.buildDict(dictionary)
  # param_2 = obj.search(searchWord)
  
  #Runtime: 111 ms, faster than 93.47% of Python3 online submissions for Implement Magic Dictionary.
  #Memory Usage: 14.2 MB, less than 80.94% of Python3 online submissions for Implement Magic Dictionary.

---

1. 1.676. Implement Magic Dictionary ↩