# LeetCode 算法题 – 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:

• The input will only have lower-case letters
• 1 <= dict words number <= 1000
• 1 <= sentence words number <= 1000
• 1 <= root length <= 100
• 1 <= sentence words length <= 1000

## 分析

1. 根据空格将句子分离为一个单词数组
2. 将单词逐个寻找其 root，有则替换，无则忽略
3. 将替换后的单词数组，用空格拼接成新句子返回

## 实现

func replaceWords(dict []string, sentence string) string {
words := strings.Split(sentence, " ")

for i := 0; i < len(words); i++ {
for _, v := range dict {
if len(words[i]) >= len(v) && words[i][:len(v)] == v {
// in order to find the shortest root, doesn't break on here
words[i] = v
}
}
}

return strings.Join(words, " ")
} 