648. 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

题目大意 #

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

现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。要求输出替换之后的句子。

解题思路 #

给出一个句子和一个可替换字符串的数组，如果句子中的单词和可替换列表里面的单词，有相同的首字母，那么就把句子中的单词替换成可替换列表里面的单词。输入最后替换完成的句子。
这一题有 2 种解题思路，第一种就是单纯的用 Map 查找。第二种是用 Trie 去替换。

代码 #


package leetcode

import "strings"

// 解法一 哈希表
func replaceWords(dict []string, sentence string) string {
	roots := make(map[byte][]string)
	for _, root := range dict {
		b := root[0]
		roots[b] = append(roots[b], root)
	}
	words := strings.Split(sentence, " ")
	for i, word := range words {
		b := []byte(word)
		for j := 1; j < len(b) && j <= 100; j++ {
			if findWord(roots, b[0:j]) {
				words[i] = string(b[0:j])
				break
			}
		}
	}
	return strings.Join(words, " ")
}

func findWord(roots map[byte][]string, word []byte) bool {
	if roots[word[0]] == nil {
		return false
	}
	for _, root := range roots[word[0]] {
		if root == string(word) {
			return true
		}
	}
	return false
}

//解法二 Trie
func replaceWords1(dict []string, sentence string) string {
	trie := Constructor208()
	for _, v := range dict {
		trie.Insert(v)
	}
	words := strings.Split(sentence, " ")
	var result []string
	word := ""
	i := 0
	for _, value := range words {
		word = ""
		for i = 1; i < len(value); i++ {
			if trie.Search(value[:i]) {
				word = value[:i]
				break
			}
		}

		if len(word) == 0 {
			result = append(result, value)
		} else {
			result = append(result, word)
		}

	}
	return strings.Join(result, " ")
}

⬅️上一页

下一页➡️