单词替换

发表于 分类于

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/replace-words

题目

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

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

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

思路

看了一眼，这好像是数据库的索引，数据库的索引是靠什么实现的呢，B+树。

好像高级软件实作中的商品图片存放位置就是按照哈希值存放在多层文件夹下。

那就构造一种树形结构存放，每个节点有26个子树。节点值存啥呢？当前位置的字符？好像没啥用。存到当前位置的字符串？不行，那可能不是一个完整的词根。那就存一个布尔值，判断是否是词根结尾。

然后写一下往树里加词根的add方法，再写一下取出给定字符串词根的check方法。之后调用这两个方法，替换字符串就行了。

总结

感谢数据结构！虽然看了一眼题解构造的字典树，真的就只是一种数据结构。

1
2
3
4
5
6
7
class Trie {
    Map<Character, Trie> children;

    public Trie() {
        children = new HashMap<Character, Trie>();
    }
}

所有的对Trie操作都在主函数中。而我写的就完全是一个类，把添加和查询操作都给封装进去了。