LeetCode 734. 句子相似性（哈希）
LeetCode 734. 句子相似性（哈希）
Michael阿明
发布于 2020-07-13 16:15:47
发布于 2020-07-13 16:15:47
1. 题目
给定两个句子 words1, words2 （每个用字符串数组表示），和一个相似单词对的列表 pairs ，判断是否两个句子是相似的。
例如，当相似单词对是 pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]]的时候，"great acting skills" 和 "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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
class Solution {
public:
bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<vector<string>>& pairs) {
if(words1.size() != words2.size())
return false;
unordered_map<string,unordered_set<string>> m;
for(auto& p : pairs)
{
m[p[0]].insert(p[1]);
m[p[1]].insert(p[0]);
}
for(int i = 0; i < words1.size(); ++i)
{
if(words1[i] == words2[i])
continue;
if(m[words1[i]].find(words2[i])==m[words1[i]].end()
&& m[words2[i]].find(words1[i])==m[words2[i]].end())
return false;
}
return true;
}
};16 ms 11.3 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录