南京建设工程公共资源交易中心网站,网站域名哪看,网站建设与维护成绩查询,微信群免费推广平台文章目录1. 题目2. 解题1. 题目
给定两个句子 words1, words2 #xff08;每个用字符串数组表示#xff09;#xff0c;和一个相似单词对的列表 pairs #xff0c;判断是否两个句子是相似的。
例如#xff0c;当相似单词对是 pairs [[great, fine每个用字符串数组表示和一个相似单词对的列表 pairs 判断是否两个句子是相似的。
例如当相似单词对是 pairs [[great, fine], [acting,drama], [skills,talent]]的时候words1 [great, acting, skills] 和 words2 [fine, drama, talent] 是相似的。
注意相似关系是 具有 传递性的。 例如如果 “great” 和 “fine” 是相似的“fine” 和 “good” 是相似的则 “great” 和 “good” 是相似的。
而且相似关系是具有对称性的。 例如“great” 和 “fine” 是相似的相当于 “fine” 和 “great” 是相似的。
并且一个单词总是与其自身相似。 例如句子 words1 [“great”], words2 [“great”], pairs [] 是相似的尽管没有输入特定的相似单词对。
最后句子只会在具有相同单词个数的前提下才会相似。 所以一个句子 words1 [“great”] 永远不可能和句子 words2 [“doubleplus”,“good”] 相似。
注
words1 and words2 的长度不会超过 1000。
pairs 的长度不会超过 2000。
每个pairs[i] 的长度为 2。
每个 words[i] 和 pairs[i][j] 的长度范围为 [1, 20]。来源力扣LeetCode 链接https://leetcode-cn.com/problems/sentence-similarity-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
数据结构–并查集Disjoint-Set
class dsu
{unordered_mapstring,string f;
public:dsu(unordered_setstring s){for(auto w : s)f[w] w;//并查集初始化}void merge(string a, string b){string fa find(a);string fb find(b);f[fa] fb;}string find(string a){string origin a;while(a ! f[a])a f[a];return f[origin] a;}
};
class Solution {
public:bool areSentencesSimilarTwo(vectorstring words1, vectorstring words2, vectorvectorstring pairs) {if(words1.size() ! words2.size())return false;unordered_setstring s;for(auto p : pairs){s.insert(p[0]);s.insert(p[1]);}dsu u(s);//并查集for(auto p : pairs)u.merge(p[0], p[1]);//mergefor(int i 0; i words1.size(); i){if(words1[i] words2[i])continue;//并查集findif(u.find(words1[i]) ! u.find(words2[i]))return false;}return true;}
};480 ms 57 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
