英语中有一个叫做词根(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”
二、解法
本题有两种解法，分别是：
1）基于哈希表的朴素查找法
2） 基于前缀树的最短前缀匹配解法
解法1的思路很直观，即将dictionary中所有的单词放在Hash Table中，然后依次匹配sentence中的每个单词。在匹配时，从每个单词中自左向右滑动窗口取其前缀，然后再Hash Table中进行查找，取最短的即可。
Original: https://www.cnblogs.com/justLittleStar/p/16454721.html
Author: LeonYi
Title: Leetcode 648 单词替换
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/566987/
转载文章受原作者版权保护。转载请注明原作者出处！