LeetCode 1258 - Synonymous Sentences

https://www.coordinate.wang/index.php/archives/2763/

给你一个近义词表 synonyms 和一个句子 text ， synonyms 表中是一些近义词对 ，你可以将句子 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"]

提示：

• 0 <= synonyms.length <= 10
• synonyms[i].length == 2
• synonyms[0] != synonyms[1]
• 所有单词仅包含英文字母，且长度最多为 10 。
• text 最多包含 10 个单词，且单词间用单个空格分隔开。

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

    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))

更加简洁的写法

    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])

https://www.acwing.com/solution/LeetCode/content/6334/

(并查集，递归枚举) $O({\mathrm{2^}}^n\cdot L)$

1. 用并查集求出来同义词组，然后通过递归的方式，枚举替换同义词。

时间复杂度

• 求同义词组的总时间复杂度近似为 $O(n)$，递归的时间复杂度为 $O(2^n\cdot L)$，其中 L 为字符串的长度（每次替换单词需要 $O(L)$ 的时间）。
• 故总时间复杂度为 $O(2^n\cdot L)$。

空间复杂度

• 并查集需要 $O(n)$ 的空间，记录答案需要 $O(2^n\cdot L)$ 的空间，故总空间复杂度为 $O(2^n\cdot L)$。

    unordered_set<string> candidates;
    unordered_map<string, string> fa;

    string find(string x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

    void solve(int idx, string& text, vector<string>& ans) {
        if (idx > text.length()) {
            ans.push_back(text);
            return;
        }

        string word;
        int i;
        for (i = idx; i < text.size() && text[i] != ' '; i++)
            word += text[i];

        i++;
        solve(i, text, ans);
        string tmp = text;

        if (fa.find(word) != fa.end()) {
            for (const string &s: candidates)
                if (word != s && find(word) == find(s)) {
                    text.replace(idx, word.length(), s);
                    solve(i - word.size() + s.size(), text, ans);
                    text = tmp;
                }
        }
    }

    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        vector<string> ans;

        for (const auto &v: synonyms) {
            fa[v[0]] = v[0];
            fa[v[1]] = v[1];
        }

        for (const auto &v: synonyms) {
            candidates.insert(v[0]);
            candidates.insert(v[1]);
            if (find(v[0]) != find(v[1]))
                fa[find(v[0])] = find(v[1]);
        }

        solve(0, text, ans);
        sort(ans.begin(), ans.end());
        return ans;
    }

https://www.cnblogs.com/seyjs/p/11878846.html

我的方法是替换，依次遍历synoyms，如果text中存在synoyms[i][0]，把text中的第一个synoyms[i][0]替换成synoyms[i][1]；同样，如果存在synoyms[i][1]，把text中的第一个synoyms[i][1]替换成synoyms[i][0]。然后再对替换过的text做同样的操作，直到不能替换位置。考虑到synoyms[i][0] = 'a'，而text中存在'an'这种情况，为了防止误替换，可以把每个单词的前后都加上'#'作为分隔。

    def generateSentences(self, synonyms, text):
        """
        :type synonyms: List[List[str]]
        :type text: str
        :rtype: List[str]
        """
        text = '#' + text.replace(' ', '#') + '#'
        queue = [text]
        for (w1,w2) in synonyms:
            for text in queue :
                newtext = text.replace('#' + w1+'#','#' + w2+'#',1)
                if newtext != text and newtext not in queue:
                    queue.append(newtext)
                newtext = text.replace('#' + w2 + '#', '#' + w1 + '#',1)
                if newtext != text and newtext not in queue:
                    queue.append(newtext)
        res = []
        for i in sorted(queue):
            newtext = i.replace('#', ' ')
            res.append(newtext[1:-1])
        return res