题目链接

力扣

题目描述

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

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

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

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"
示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"
示例 3：

输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
输出："a a a a a a a a bbb baba a"
示例 4：

输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"
示例 5：

输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
输出："it is ab that this solution is ac"
 

提示：

1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写字母组成。
1 <= sentence.length <= 10^6
sentence 仅由小写字母和空格组成。
sentence 中单词的总量在范围 [1, 1000] 内。
sentence 中每个单词的长度在范围 [1, 1000] 内。
sentence 中单词之间由一个空格隔开。
sentence 没有前导或尾随空格。

解题思路

前缀树

代码

Python

class Trie:
    def __init__(self):
        self.childs = [None for _ in range(26)]
        self.isEnd = False
 
 
class Solution:
    def findPrefix(self, node: Trie, prefix: str) -> str:
        for i in range(len(prefix)):
            idx = ord(prefix[i]) - ord('a')
            if node.childs[idx]:
                if node.childs[idx].isEnd:
                    return prefix[:i + 1]
            else:
                return prefix
            node = node.childs[idx]
        return prefix
 
    def insert(self, node: Trie, word: str) -> None:
        for i in range(len(word)):
            idx = ord(word[i]) - ord('a')
            if not node.childs[idx]:
                node.childs[idx] = Trie()
            node = node.childs[idx]
        node.isEnd = True
 
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        root = Trie()
        for word in dictionary:
            self.insert(root, word)
        sentenceSplit = str.split(sentence, ' ')
        for i in range(len(sentenceSplit)):
            sentenceSplit[i] = self.findPrefix(root, sentenceSplit[i])
        return ' '.join(sentenceSplit)

Go

type Trie struct {
	childs [26]*Trie
	isEnd  bool
}
 
func Constructor() Trie {
	return Trie{}
}
 
func (this *Trie) findPrefix(prefix string) string {
	node := this
	for i, chr := range prefix {
		idx := chr - 'a'
		if node.childs[idx] != nil {
			if node.childs[idx].isEnd {
				return prefix[:i+1]
			}
		} else {
			return prefix
		}
		node = node.childs[idx]
	}
	return prefix
}
 
func (this *Trie) insert(word string) {
	node := this
	for _, chr := range word {
		idx := chr - 'a'
		if node.childs[idx] == nil {
			node.childs[idx] = &Trie{}
		}
		node = node.childs[idx]
	}
	node.isEnd = true
}
 
func replaceWords(dictionary []string, sentence string) string {
	root := Constructor()
	for _, word := range dictionary {
		root.insert(word)
	}
	sentenceSplit := strings.Split(sentence, " ")
	ans := ""
	for _, word := range sentenceSplit {
		ans += root.findPrefix(word) + " "
	}
	return ans[:len(ans)-1]
}