宫水三叶的刷题日记

V1

2022/07/11阅读:24主题:全栈蓝

676. 实现一个魔法字典 : 结合 DFS 的 Trie 运用题

题目描述

这是 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, falsetruefalsefalse]

解释
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

提示:

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

Trie + DFS

为了方便,我们令 dictionaryss,令 searchWords

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

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

  • buildDict 操作:我们可以将所有的 存入字典树中,方便后续检索;

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

不了解「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 < 0return 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] == 0continue;
            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, 001);
    }
}
  • 时间复杂度:buildDict 操作需要将所有字符存入 Trie,复杂度为 search 操作在不考虑 limit 以及字典树中最多只有 具体方案所带来的剪枝效果的话,最坏情况下要搜索所有 个方案,其中 为字符集大小, 为搜索字符串的最大长度
  • 空间复杂度: ,其中 为存入 Trie 的最大方案数, 为存入字符串的最大长度, 为字符集大小

最后

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

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

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

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

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1