mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 01:15:57 +08:00
40 lines
1.9 KiB
Markdown
Executable File
40 lines
1.9 KiB
Markdown
Executable File
# [648. Replace Words](https://leetcode.com/problems/replace-words/)
|
||
|
||
|
||
## 题目
|
||
|
||
In English, we have a concept called `root`, which can be followed by some other words to form another longer word - let's call this word `successor`. For example, the root `an`, followed by `other`, which can form another word `another`.
|
||
|
||
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the `successor` in the sentence with the `root` forming it. If a `successor` has many `roots` can form it, replace it with the root with the shortest length.
|
||
|
||
You need to output the sentence after the replacement.
|
||
|
||
**Example 1:**
|
||
|
||
Input: dict = ["cat", "bat", "rat"]
|
||
sentence = "the cattle was rattled by the battery"
|
||
Output: "the cat was rat by the bat"
|
||
|
||
**Note:**
|
||
|
||
1. The input will only have lower-case letters.
|
||
2. 1 <= dict words number <= 1000
|
||
3. 1 <= sentence words number <= 1000
|
||
4. 1 <= root length <= 100
|
||
5. 1 <= sentence words length <= 1000
|
||
|
||
|
||
## 题目大意
|
||
|
||
在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
|
||
|
||
现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。要求输出替换之后的句子。
|
||
|
||
|
||
|
||
## 解题思路
|
||
|
||
|
||
- 给出一个句子和一个可替换字符串的数组，如果句子中的单词和可替换列表里面的单词，有相同的首字母，那么就把句子中的单词替换成可替换列表里面的单词。输入最后替换完成的句子。
|
||
- 这一题有 2 种解题思路，第一种就是单纯的用 Map 查找。第二种是用 Trie 去替换。
|