题目形容

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

Tag : 「字典树」、「DFS」

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

实现 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"); // 返回 FalsemagicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 能够匹配 "hello" ，所以返回 TruemagicDictionary.search("hell"); // 返回 FalsemagicDictionary.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 利用面」介绍

代码：

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);    }}
  • 工夫复杂度：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$ 为字符集大小

最初

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

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

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。

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

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地

本文由mdnice多平台公布