LC 676. 实现一个魔法字典

题目描述

这是 LeetCode 上的 676. 实现一个魔法字典 ，难度为中等。

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词互不相同。如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord，判定能否只将字符串中一个字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true；否则，返回 false。

示例：

输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]

输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

提示：

$1 <= dictionary.length <= 100$
$1 <= dictionary[i].length <= 100$
dictionary[i] 仅由小写英文字母组成
dictionary 中的所有字符串互不相同
$1 <= searchWord.length <= 100$
searchWord 仅由小写英文字母组成
buildDict 仅在 search 之前调用一次
最多调用 $100$ 次 search

Trie + DFS

为了方便，我们令 dictionary 为 ss，令 searchWord 为 s。

整体题意：给定字符串 s，问能否存在替换掉 s 中的某个字符，使得新字符串出现在 ss 数组中。

考虑如何使用「字典树/Trie」求解该问题：

buildDict 操作：我们可以将所有的 $ss[i]$ 存入字典树中，方便后续检索；
search 操作：设计递归函数 boolean query(String s, int idx, int p, int limit)，其中 s 为待检索的字符串，idx 为当前处理到字符串 s 的哪一位，p 为当前搜索到字典树的索引编号（起始有 $p = 0$），limit 为当前剩余的替换字符次数，根据题意，limit 固定为 $1$，含义为必须替换掉 s 的一个字符。
对于 $s[idx]$ 而言，我们可以枚举新字符串在当前位置是何种字符（$C = 26$ 个选择），若当前枚举到的字符与 $s[idx]$ 一致，则不消耗替换次数。
爆搜过程中替换次数为负数直接剪枝，当爆搜到结尾位置，再检查当前的字典树索引 $p$ 是否为单词结尾节点（对应查询数组 ss 中是否存在该字符串），以及剩余的替换次数 limit 是否为 $0$。

不了解「Trie / 字典树」的同学可以看前置 🧀：字典树入门。里面通过图例展示了字典树基本形态，以及提供了「数组实现」和「TrieNode 实现」两种方式，还有「数组大小估算方式」和「Trie 应用面」介绍

Java 代码：

class MagicDictionary {
    int N = 100 * 100, M = 26, idx = 0;
    int[][] tr = new int[N][M];
    boolean[] isEnd = new boolean[N * M];
    void add(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        isEnd[p] = true;
    }
    boolean query(String s, int idx, int p, int limit) {
        if (limit < 0) return false;
        if (idx == s.length()) return isEnd[p] && limit == 0;
        int u = s.charAt(idx) - 'a';
        for (int i = 0; i < 26; i++) {
            if (tr[p][i] == 0) continue;
            if (query(s, idx + 1, tr[p][i], i == u ? limit : limit - 1)) return true;
        }
        return false;
    }
    public void buildDict(String[] ss) {
        for (String s : ss) add(s);
    }
    public boolean search(String s) {
        return query(s, 0, 0, 1);
    }
}

TypeScript 代码：

class MagicDictionary {
    N: number = 100 * 100; M: number = 26; idx: number = 0;
    tr: number[][] = new Array<Array<number>>(this.N)
    isEnd: boolean[] = new Array<boolean>(this.N * this.M).fill(false)
    add(s: string): void {
        let p = 0
        for (let i = 0; i < s.length; i++) {
            const u = s.charCodeAt(i) - 'a'.charCodeAt(0)
            if (this.tr[p] == undefined) this.tr[p] = new Array<number>(this.M).fill(0)
            if (this.tr[p][u] == 0) this.tr[p][u] = ++this.idx
            p = this.tr[p][u]
        }
        this.isEnd[p] = true
    }
    query(s: string, idx: number, p: number, limit: number): boolean {
        if (limit < 0) return false
        if (idx == s.length) return this.isEnd[p] && limit == 0
        const u = s.charCodeAt(idx) - 'a'.charCodeAt(0)
        for (let i = 0; i < 26; i++) {
            if (this.tr[p] == undefined || this.tr[p][i] == 0) continue
            if (this.query(s, idx + 1, this.tr[p][i], i == u ? limit : limit - 1)) return true
        }
        return false
    }
    buildDict(ss: string[]): void {
        for (const s of ss) this.add(s)
    }
    search(s: string): boolean {
        return this.query(s, 0, 0, 1)
    }
}

时间复杂度：buildDict 操作需要将所有字符存入 Trie，复杂度为 $\sum_{i = 0}^{n - 1} len(ss[i]])$；search 操作在不考虑 limit 以及字典树中最多只有 $100$ 具体方案所带来的剪枝效果的话，最坏情况下要搜索所有 $C^L$ 个方案，其中 $C = 26$ 为字符集大小，$L = 100$ 为搜索字符串的最大长度
空间复杂度：$O(N \times L \times C)$，其中 $N = 100$ 为存入 Trie 的最大方案数，$L = 100$ 为存入字符串的最大长度，$C = 26$ 为字符集大小

模拟

当然，利用数据范围只有 $100$，直接使用模拟也是可以的。

Java 代码：

class MagicDictionary {
    String[] ss;
    public void buildDict(String[] _ss) {
        ss = _ss;
    }
    public boolean search(String str) {
        for (String s : ss) {
            int cnt = 0;
            for (int i = 0; s.length() == str.length() && i < s.length() && cnt <= 1; i++) {
                if (s.charAt(i) != str.charAt(i)) cnt++;
            }
            if (cnt == 1) return true;
        }
        return false;
    }
}

TypeScript 代码：

class MagicDictionary {
    ss: string[]
    buildDict(_ss: string[]): void {
        this.ss = _ss
    }
    search(s: string): boolean {
        for (const str of this.ss) {
            let cnt = 0
            for (let i = 0; str.length == s.length && i < s.length && cnt <= 1; i++) {
                if (s.charAt(i) != str.charAt(i)) cnt++
            }
            if (cnt == 1) return true
        }
        return false
    }
}

时间复杂度：buildDict 操作复杂度为 $O(1)$；search 操作复杂度为 $O(n \times L)$，其中 $n$ 为数组 ss 的长度，$L$ 为查询字符串的长度
空间复杂度：$O(n)$

加餐

前置练习题可用 Trie 进阶的模拟题
另外一道结合 DFS 的 Trie 运用题

最后

这是我们「刷穿 LeetCode」系列文章的第 No.676 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

DFS 字典树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 1252. 奇数值单元格的数目上一篇

LC 741. 摘樱桃下一篇