网站平台搭建和维护需要什么,北京一网数据软件有限公司,宜春静态管理,普宁17网站一起做网店文章目录1. 题目2. 解题1. 题目
给你一个近义词表 synonyms 和一个句子 text #xff0c; synonyms 表中是一些近义词对 #xff0c;你可以将句子 text 中每个单词用它的近义词来替换。
请你找出所有用近义词替换后的句子#xff0c;按 字典序排序 后返回。
示例 1#…
文章目录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
{vectorint 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_mapstring, int w_id;//单词 id映射unordered_mapint, string id_w;//id 单词unordered_mapint, vectorstring f_words;//近义词代表id, 近义词集合vectorstring ans;//答案
public:vectorstring generateSentences(vectorvectorstring 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());//近义词排序vectorstring 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(vectorstring 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, i1, 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, i1, path, u);path.resize(size);//回溯}}}
};4 ms 8.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
