676.实现一个魔法字典

链接：676.实现一个魔法字典
难度：Medium
标签：深度优先搜索、设计、字典树、哈希表、字符串
简介：设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

题解 1 - typescript

• 编辑时间：2021-11-05
• 执行用时：132ms
• 内存消耗：45.9MB
• 编程语言：typescript
• 解法介绍：trie。

const getIdx = (ch: string) => ch.codePointAt(0)! - 'a'.codePointAt(0)!;
class TrieNode {
  end = false;
  children: TrieNode[] = [];
  constructor(public val: string) {}
}
class Trie {
  root = new TrieNode('');
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      const idx = getIdx(ch);
      if (!node.children[idx]) node.children[idx] = new TrieNode(ch);
      node = node.children[idx];
    }
    node.end = true;
  }
  search(word: string): boolean {
    return this._search(word);
  }
  _search(word: string, node = this.root, idx = 0, err = 1): boolean {
    if (idx === word.length) return node.end && err === 0;
    const ch = word[idx];
    const chIdx = getIdx(ch);
    if (node.children[chIdx] && this._search(word, node.children[chIdx], idx + 1, err)) return true;
    if (err === 0) return false;
    for (const child of node.children) {
      if (child === node.children[chIdx]) continue;
      if (this._search(word, child, idx + 1, err - 1)) return true;
    }
    return false;
  }
}
class MagicDictionary {
  trie = new Trie();
  buildDict(dictionary: string[]): void {
    dictionary.forEach(word => this.trie.insert(word));
  }
  search(searchWord: string): boolean {
    return this.trie.search(searchWord);
  }
}

题解 2 - cpp

• 编辑时间：2022-07-11
• 执行用时：712ms
• 内存消耗：101.6MB
• 编程语言：cpp
• 解法介绍：trie, 对于每种可能出现 1 个替换，进行递归考虑。

#define CHILD_SIZE 26
class TrieNode {
   public:
    int key;
    bool end;
    TrieNode **children;
    TrieNode(int key) {
        this->key = key;
        this->end = false;
        this->children = (TrieNode **)malloc(sizeof(TrieNode *) * CHILD_SIZE);
        for (int i = 0; i < CHILD_SIZE; i++) children[i] = nullptr;
    }
};
class Trie {
   public:
    TrieNode *root;
    Trie() { this->root = new TrieNode(0); }
    void insert(string words) {
        TrieNode *node = root;
        for (auto &w : words) {
            if (node->children[w - 'a'] == nullptr)
                node->children[w - 'a'] = new TrieNode(w);
            node = node->children[w - 'a'];
        }
        node->end = true;
    }
    bool search(string words) { return _search(words, 0, root, 0); }
    bool _search(string &words, int idx, TrieNode *node, int replaceCnt) {
        int w = words[idx];
        if (idx == words.size() - 1) {
            if (replaceCnt > 1)
                return false;
            else if (replaceCnt == 1)
                return node->children[w - 'a'] != nullptr &&
                       node->children[w - 'a']->end;
            else {
                for (int i = 0; i < CHILD_SIZE; i++) {
                    if (node->children[i] == nullptr || w - 'a' == i) continue;
                    if (node->children[i]->end) return true;
                }
            }
            return false;
        }
        int nextw = words[idx + 1];
        for (int i = 0; i < CHILD_SIZE; i++) {
            if (node->children[i] == nullptr) continue;
            if (w - 'a' == i &&
                _search(words, idx + 1, node->children[i], replaceCnt))
                return true;
            if (w - 'a' != i &&
                _search(words, idx + 1, node->children[i], replaceCnt + 1))
                return true;
        }
        return false;
    }
};
class MagicDictionary {
   public:
    Trie *trie;
    MagicDictionary() { trie = new Trie(); }
    void buildDict(vector<string> dictionary) {
        for (auto &words : dictionary) trie->insert(words);
    }
    bool search(string searchWord) { return trie->search(searchWord); }
};

题解 3 - python

• 编辑时间：2024-08-13
• 执行用时：239ms
• 内存消耗：20.96MB
• 编程语言：python
• 解法介绍：字典树。

class TrieNode:
    def __init__(self, c) -> None:
        self.ch = c
        self.end = False
        self.children: List[TrieNode] = [None] * 26
    def add(self, s: str):
        node = self
        for c in s:
            idx = ord(c) - ord('a')
            if not node.children[idx]: node.children[idx] = TrieNode(c)
            node = node.children[idx]
        node.end = True
class MagicDictionary:
    def __init__(self):
        self.trie = TrieNode('')
    def buildDict(self, dictionary: List[str]) -> None:
        for v in dictionary: self.trie.add(v)
    def search(self, searchWord: str) -> bool:
        return self._search(searchWord, self.trie, False)
    def _search(self, searchWord: str, node: 'TrieNode', f: bool) -> bool:
        if searchWord == '': return node.end and f
        idx = ord(searchWord[0]) - ord('a')
        if not node.children[idx]:
            if f: return False
            return any(
                self._search(searchWord[1:], next_node, True)
                for next_node in node.children
                if next_node
            )
        return self._search(searchWord[1:], node.children[idx], f) or \
        (not f and any(
            self._search(searchWord[1:], next_node, True)
            for next_node in node.children
            if next_node and next_node != node.children[idx]
        ))