列表

详情

剑指 Offer II 063. 替换单词

在英语中，有一个叫做 词根(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"

 

提示：

 

注意：本题与主站 648 题相同： https://leetcode.cn/problems/replace-words/

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: string replaceWords(vector<string>& dictionary, string sentence) { } };

golang 解法, 执行用时: 32 ms, 内存消耗: 16.9 MB, 提交时间: 2022-11-17 16:20:15 

func replaceWords(dictionary []string, sentence string) string {
    type trie map[rune]trie
    root := trie{}
    for _, s := range dictionary {
        cur := root
        for _, c := range s {
            if cur[c] == nil {
                cur[c] = trie{}
            }
            cur = cur[c]
        }
        cur['#'] = trie{}
    }

    words := strings.Split(sentence, " ")
    for i, word := range words {
        cur := root
        for j, c := range word {
            if cur['#'] != nil {
                words[i] = word[:j]
                break
            }
            if cur[c] == nil {
                break
            }
            cur = cur[c]
        }
    }
    return strings.Join(words, " ")
}

python3 解法, 执行用时: 60 ms, 内存消耗: 28.7 MB, 提交时间: 2022-11-17 16:19:51 

'''
与哈希集合不同，我们用 dictionary 中所有词根构建一棵字典树，并用特殊符号标记结尾。
在搜索前缀时，只需在字典树上搜索出一条最短的前缀路径即可。
'''
class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = {}
        for word in dictionary:
            cur = trie
            for c in word:
                if c not in cur:
                    cur[c] = {}
                cur = cur[c]
            cur['#'] = {}

        words = sentence.split(' ')
        for i, word in enumerate(words):
            cur = trie
            for j, c in enumerate(word):
                if '#' in cur:
                    words[i] = word[:j]
                    break
                if c not in cur:
                    break
                cur = cur[c]
        return ' '.join(words)

golang 解法, 执行用时: 20 ms, 内存消耗: 7.5 MB, 提交时间: 2022-11-17 16:18:24 

func replaceWords(dictionary []string, sentence string) string {
    dictionarySet := map[string]bool{}
    for _, s := range dictionary {
        dictionarySet[s] = true
    }
    words := strings.Split(sentence, " ")
    for i, word := range words {
        for j := 1; j <= len(word); j++ {
            if dictionarySet[word[:j]] {
                words[i] = word[:j]
                break
            }
        }
    }
    return strings.Join(words, " ")
}

python3 解法, 执行用时: 240 ms, 内存消耗: 19.1 MB, 提交时间: 2022-11-17 16:17:37 

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        ds = set(dictionary)
        words = sentence.split(' ')
        for i, word in enumerate(words):
            for j in range(1, len(word)+1):
                if word[:j] in ds:
                    words[i] = word[:j]
                    break
        return ' '.join(words)

上一题

© 2024 leetcode.cn