Leetcode 1258:近义词句子(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1258:近义词句子(超详细的解法!!!)

in leetcode with 0 comment

给你一个近义词表 synonyms 和一个句子 textsynonyms 表中是一些近义词对 ,你可以将句子 text 中每个单词用它的近义词来替换。

请你找出所有用近义词替换后的句子,按 字典序排序 后返回。

示例 1:

输入:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
输出:
["I am cheerful today but was sad yesterday",
"I am cheerful today but was sorrow yesterday",
"I am happy today but was sad yesterday",
"I am happy today but was sorrow yesterday",
"I am joy today but was sad yesterday",
"I am joy today but was sorrow yesterday"]

提示:

解题思路

首先观察题目,发现相同近义词可能有很多个,所以不难想到通过并查集找到所有的集合。然后单词替换问题,实际上就是Leetcode 78:子集(最详细的解法!!!)

class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        parent = collections.defaultdict(str)
        data = collections.defaultdict(list)
        
        def find(x):
            if x not in parent:
                parent[x] = x
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]
        
        for p, q in synonyms:
            x, y = find(p), find(q)
            if x != y:
                parent[x] = y
        for k in parent:
            data[find(k)].append(k)

        res, texList = set(), text.split(" ")
        def dfs(index, path):
            res.add(" ".join(path))
            for i in range(index, len(texList)):
                for t in data[find(texList[i])]:
                    cur = path[:]
                    cur[i] = t
                    dfs(i + 1, cur)
                    dfs(i + 1, path)
        dfs(0, texList)
        return sorted(list(res))

更加简洁的写法

class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        parent = collections.defaultdict(str)
        data = collections.defaultdict(list)
        
        def find(x):
            if x not in parent:
                parent[x] = x
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]
        
        for p, q in synonyms:
            x, y = find(p), find(q)
            if x != y:
                parent[x] = y
        for k in parent:
            data[find(k)].append(k)
            
        res = [[]]
        for w in text.split(" "):
            res = [it + [v] for it in res for v in data[find(w)] or [w]]
        return sorted([" ".join(it) for it in res])

reference:

https://leetcode.com/problems/synonymous-sentences/discuss/430534/Python-bfs-solution

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses