Skip to content

648.单词替换.md

Latest commit

 

History

History
137 lines (106 loc) · 4.96 KB

648.单词替换.md

File metadata and controls

137 lines (106 loc) · 4.96 KB
Raw

648.单词替换

https://leetcode-cn.com/problems/replace-words/solution/648dan-ci-ti-huan-bao-li-yu-qian-zhui-sh-2ktv/

难度：中等

题目：

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

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

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

提示：

  • 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 没有前导或尾随空格。

示例：

示例 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列表转化为集合，增加检索速度
  2. 然后把句子拆分成每个单词，针对每个单词进行循环匹配
  3. 创建一个列表，用于记录个单词的匹配结果
  4. 每个单词从第一位开始循环，判断是否在集合中，如果找到将当字符串的长度加入列表，最终未找到则将原词加入列表
  5. 最终将列表拼接为字符串返回即可。

执行用时较长：

那么这道题正确的解题思路是什么呢？如果你还不了解前缀树的知识，建议大家先看看这道题目：

代码使用了手写实现前缀树的方式，主要是为了复习前缀树的知识，具体实现如下

  1. 先将dictionary列表中的每个元素插入前缀树中
  2. 然后循环每个单词判断是包含在前缀树中，若包含返回最短前缀树，不包含返回原单词
  3. 最终将列表拼接为字符串返回即可。

执行超过100% python用户：

暴力解题

class Solution:
    def replaceWords(self, dictionary, sentence):
        prefix = set(dictionary)
        ret = []
        for strs in sentence.split():
            for i in range(1,len(strs)):
                if strs[:i] in prefix:
                    ret.append(strs[:i])
                    break
            else:
                ret.append(strs)
        return ' '.join(ret)

前缀树解题：

class Solution:
    def __init__(self):
        self.dic = {}

    def insert(self, strs):
        tmp = self.dic
        for s in strs:
            if s not in tmp:
                tmp[s] = {}
            tmp = tmp[s]
        tmp['is_word'] = True

    def search(self, strs):
        ret = []
        tmp = self.dic
        for s in strs:
            if s not in tmp:
                return False
            ret.append(s)
            tmp = tmp[s]
            if tmp.get('is_word'):
                return ret
        return ret if tmp else False

    def replaceWords(self, dictionary, sentence):
        for strs in dictionary:
            self.insert(strs)
        stack = []
        for word in sentence.split():
            result = self.search(word)
            if result:
                word = ''.join(result)
            stack.append(word)
        return ' '.join(stack)

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown