当前位置：网站首页>648. 单词替换 : 字典树的经典运用

648. 单词替换 : 字典树的经典运用

2022-07-07 11:31:00 【宫水三叶的刷题日记】

题目描述

这是 LeetCode 上的 648. 单词替换 ，难度为中等。

Tag : 「字典树」

在英语中，我们有一个叫做词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"

输出："a a b c"

提示：

dictionary[i] 仅由小写字母组成。
sentence 仅由小写字母和空格组成。
sentence 中单词的总量在范围内。
sentence 中每个单词的长度在范围内。
sentence 中单词之间由一个空格隔开。
sentence 没有前导或尾随空格。

基本分析

这是一道 Trie 的模板题，还不了解 Trie 的同学可以先看前置：【设计数据结构】实现 Trie (前缀树)

前置通过图解形式讲解了 Trie 的结构与原理，以及提供了两种实现 Trie 的方式。

回到本题，为了方便，我们令 ds 为 dictionary，令 s 为 sentence。

二维数组

一个比较习惯的做法，是使用「二维数组」来实现 Trie，配合 static 优化，可以有效控制 new 的次数，耗时相对稳定。

考虑两个 Trie 的基本操作：

add 操作：变量入参字符串 s，将字符串中的每位字符映射到，同时为了能够方便查询某个字符串（而不只是某个前缀）是否曾经存入过 Trie 中，额外使用一个布尔数组 isEnd 记录某个位置是否为单词结尾。
query 操作：

至于二维数组的大小估算，可以直接开成，其中为要插入到 Trie 中的字符总数，为对应的字符集大小。在没有 MLE 风险时，可以直接开这么多；而当较大（超过，甚至时），可以适当将中的减少，使得总空间在左右，因为实际上由于二维数组中的某些行中会存储一个字符以上，实际上我们用不到这么多行。

代码（不使用 static 优化，耗时增加十倍）：

class Solution {
    static int N = 100000, M = 26;
    static int[][] tr = new int[N][M];
    static boolean[] isEnd = new boolean[N * M];
    static int idx;
    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;
    }
    String query(String s) {
        for (int i = 0, p = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) break;
            if (isEnd[tr[p][u]]) return s.substring(0, i + 1);
            p = tr[p][u];
        }
        return s;
    }
    public String replaceWords(List<String> ds, String s) {
        for (int i = 0; i <= idx; i++) {
            Arrays.fill(tr[i], 0);
            isEnd[i] = false;
        }
        for (String d : ds) add(d);
        StringBuilder sb = new StringBuilder();
        for (String str : s.split(" ")) sb.append(query(str)).append(" ");
        return sb.substring(0, sb.length() - 1);
    }
}

时间复杂度：令，为 s 长度，复杂度为
空间复杂度：，其中为字符集大小

TrieNode

另外一个能够有效避免「估数组大小」操作的方式，是使用 TrieNode 的方式实现 Trie：每次使用到新的格子再触发 new 操作。

至于为什么有了 TrieNode 的方式，我还是会采用「二维数组」优先的做法，在知乎上有同学问过我类似的问题，只不过原问题是「为什么有了动态开点线段树，直接 build 出空间的做法仍有意义」，这对应到本题使用「二维数组」还是「TrieNode」是一样的道理：

除非某些语言在启动时，采用虚拟机的方式，并且预先分配了足够的内存，否则所有的 new 操作都需要反映到 os 上，而在 linux 分配时需要遍历红黑树，因此即使是总空间一样，一次性的 new 要比多次小空间的 new 更省时间，同时集中性的 new 也比分散性的 new 操作要更快，这也就是为什么我们不无脑使用 TrieNode 的原因。

代码：

class Solution {
    class Node {
        boolean isEnd;
        Node[] tns = new Node[26];
    }
    Node root = new Node();
    void add(String s) {
        Node p = root;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new Node();
            p = p.tns[u];
        }
        p.isEnd = true;
    }
    String query(String s) {
        Node p = root;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) break;
            if (p.tns[u].isEnd) return s.substring(0, i + 1);
            p = p.tns[u];
        }
        return s;
    }
    public String replaceWords(List<String> ds, String s) {
        for (String str : ds) add(str);
        StringBuilder sb = new StringBuilder();
        for (String str : s.split(" ")) sb.append(query(str)).append(" ");
        return sb.substring(0, sb.length() - 1);
    }
}