676. Implement Magic Dictionary

Approach 1: Hash Table

• Time:
  • Constructor: $O(1)$
  • buildDict(dictionary: list[str]): $O(\Sigma |\texttt{dictionary[i]}|^2)$ search(searchWord: str): $O(|\texttt{searchWord}|^2)$
• Space: $O(\Sigma |\texttt{dictionary[i]}|)$

C++JavaPython

class MagicDictionary {
 public:
  void buildDict(vector<string> dictionary) {
    for (const string& word : dictionary)
      for (int i = 0; i < word.length(); ++i) {
        const string replaced = getReplaced(word, i);
        dict[replaced] = dict.contains(replaced) ? '*' : word[i];
      }
  }

  bool search(string searchWord) {
    for (int i = 0; i < searchWord.length(); ++i) {
      const string replaced = getReplaced(searchWord, i);
      if (const auto it = dict.find(replaced);
          it != dict.cend() && it->second != searchWord[i])
        return true;
    }
    return false;
  }

 private:
  unordered_map<string, char> dict;

  string getReplaced(const string& s, int i) {
    return s.substr(0, i) + '*' + s.substr(i + 1);
  }
};

class MagicDictionary {
  public void buildDict(String[] dictionary) {
    for (final String word : dictionary)
      for (int i = 0; i < word.length(); ++i) {
        final String replaced = getReplaced(word, i);
        dict.put(replaced, dict.containsKey(replaced) ? '*' : word.charAt(i));
      }
  }

  public boolean search(String searchWord) {
    for (int i = 0; i < searchWord.length(); ++i) {
      final String replaced = getReplaced(searchWord, i);
      if (dict.getOrDefault(replaced, searchWord.charAt(i)) != searchWord.charAt(i))
        return true;
    }
    return false;
  }

  private Map<String, Character> dict = new HashMap<>();

  private String getReplaced(final String s, int i) {
    return s.substring(0, i) + '*' + s.substring(i + 1);
  }
}

class MagicDictionary:
  def __init__(self):
    self.dict = {}

  def buildDict(self, dictionary: list[str]) -> None:
    for word in dictionary:
      for i, c in enumerate(word):
        replaced = self._getReplaced(word, i)
        self.dict[replaced] = '*' if replaced in self.dict else c

  def search(self, searchWord: str) -> bool:
    for i, c in enumerate(searchWord):
      replaced = self._getReplaced(searchWord, i)
      if self.dict.get(replaced, c) != c:
        return True
    return False

  def _getReplaced(self, s: str, i: int) -> str:
    return s[:i] + '*' + s[i + 1:]

Approach 2: Trie

• Time:
  • Constructor: $O(1)$
  • buildDict(dictionary: list[str]): $O(\Sigma |\texttt{dictionary[i]}|)$
  • search(searchWord: str): $O(26|\texttt{searchWord}| \cdot k)$, where $k$ is average number of children a node has
• Space: $O(\Sigma |\texttt{dictionary[i]}|)$

C++JavaPython

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  bool isWord = false;
  TrieNode() : children(26) {}
};

class MagicDictionary {
 public:
  void buildDict(vector<string> dictionary) {
    for (const string& word : dictionary)
      insert(word);
  }

  bool search(string searchWord) {
    shared_ptr<TrieNode> node = root;
    for (int i = 0; i < searchWord.length(); ++i) {
      const int index = searchWord[i] - 'a';
      for (int j = 0; j < 26; ++j) {
        if (j == index)
          continue;
        shared_ptr<TrieNode> child = node->children[j];
        if (child == nullptr)
          continue;
        // Replace the searchWord[i] with ('a' + j), then check if
        // searchWord[i + 1..n) matches `child`.
        if (find(child, searchWord, i + 1))
          return true;
      }
      if (node->children[index] == nullptr)
        return false;
      node = node->children[index];
    }
    return false;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();

  void insert(const string& word) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
    }
    node->isWord = true;
  }

  bool find(shared_ptr<TrieNode> node, const string& word, int s) {
    for (int i = s; i < word.length(); ++i) {
      const int index = word[i] - 'a';
      if (node->children[index] == nullptr)
        return false;
      node = node->children[index];
    }
    return node->isWord;
  }
};

class TrieNode {
  public TrieNode[] children = new TrieNode[26];
  public boolean isWord = false;
}

class MagicDictionary {
  public void buildDict(String[] dictionary) {
    for (final String word : dictionary)
      insert(word);
  }

  public boolean search(String searchWord) {
    TrieNode node = root;
    for (int i = 0; i < searchWord.length(); ++i) {
      final int index = searchWord.charAt(i) - 'a';
      for (int j = 0; j < 26; ++j) {
        if (j == index)
          continue;
        TrieNode child = node.children[j];
        if (child == null)
          continue;
        // Replace the searchWord[i] with ('a' + j), then check if
        // searchWord[i + 1..n) matches `child`.
        if (find(child, searchWord, i + 1))
          return true;
      }
      if (node.children[index] == null)
        return false;
      node = node.children[index];
    }
    return false;
  }

  private TrieNode root = new TrieNode();

  private void insert(final String word) {
    TrieNode node = root;
    for (final char c : word.toCharArray()) {
      final int i = c - 'a';
      if (node.children[i] == null)
        node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.isWord = true;
  }

  private boolean find(TrieNode node, final String word, int s) {
    for (int i = s; i < word.length(); ++i) {
      final int index = word.charAt(i) - 'a';
      if (node.children[index] == null)
        return false;
      node = node.children[index];
    }
    return node.isWord;
  }
}

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = collections.defaultdict(TrieNode)
    self.isWord = False


class MagicDictionary:
  def __init__(self):
    self.root = TrieNode()

  def buildDict(self, dictionary: list[str]) -> None:
    for word in dictionary:
      self._insert(word)

  def search(self, searchWord: str) -> bool:
    node: TrieNode = self.root
    for i, c in enumerate(searchWord):
      for letter in string.ascii_lowercase:
        if letter == c:
          continue
        child = node.children[letter]
        if not child:
          continue
        # Replace the searchWord[i] with `letter`, then check if
        # searchWord[i + 1..n) matches `child`.
        if self._find(child, searchWord, i + 1):
          return True
      if not node.children[c]:
        return False
      node = node.children[c]
    return False

  def _insert(self, word: str) -> None:
    node: TrieNode = self.root
    for c in word:
      node = node.children.setdefault(c, TrieNode())
    node.isWord = True

  def _find(self, node: TrieNode, word: str, i: int) -> bool:
    for c in word[i:]:
      if c not in node.children:
        return False
      node = node.children[c]
    return node.isWord