文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個近義詞表 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）
鏈接：https://leetcode-cn.com/problems/synonymous-sentences
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class dsu {vector<int> f; public:dsu(int n){f.resize(n);for(int i = 0; i < n; ++i)f[i] = i;}void merge(int a, int b){int fa = find(a);int fb = find(b);f[fa] = fb;}int find(int a){int origin = a;while(a != f[a])a = f[a];return f[origin] = a;} }; class Solution {unordered_map<string, int> w_id;//單詞 id映射unordered_map<int, string> id_w;//id 單詞unordered_map<int, vector<string>> f_words;//近義詞代表id, 近義詞集合vector<string> ans;//答案 public:vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {int i = 0;for(auto& s : synonyms){if(!w_id.count(s[0])){w_id[s[0]] = i;id_w[i++] = s[0];}if(!w_id.count(s[1])){w_id[s[1]] = i;id_w[i++] = s[1];}}int n = w_id.size(), i1, i2, f;//并查集找集合dsu u(n);for(auto& s : synonyms){i1 = w_id[s[0]];i2 = w_id[s[1]];u.merge(i1, i2);//近義詞合并}for(i = 0; i < n; ++i){f = u.find(i);//近義詞代表的idf_words[f].push_back(id_w[i]);//加入集合}for(auto& fw : f_words)sort(fw.second.begin(), fw.second.end());//近義詞排序vector<string> sentenceWords;//獲取句子里的單詞string w;for(int i = 0; i < text.size(); ++i){if(text[i] == ' ' || i == text.size()-1){if(i == text.size()-1) w += text[i];sentenceWords.push_back(w);w = "";}elsew += text[i];}string path;bt(sentenceWords, 0, path, u);//回溯生成句子return ans;}void bt(vector<string>& sentenceWords, int i, string& path, dsu& u){if(i == sentenceWords.size()){path.pop_back();//空格ans.push_back(path);return;}int size = path.size();if(!w_id.count(sentenceWords[i])){ //沒有近義詞path += sentenceWords[i]+" ";bt(sentenceWords, i+1, path, u);path.resize(size);//回溯}else{int f = u.find(w_id[sentenceWords[i]]);//有近義詞，近義詞的代表ffor(int j = 0; j < f_words[f].size(); ++j)//遍歷近義詞集合{path += f_words[f][j]+" ";bt(sentenceWords, i+1, path, u);path.resize(size);//回溯}}} };

4 ms 8.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1258. 近义词句子（哈希+并查集+排序+回溯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。