class Solution {
public:
bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
}
};
734. 句子相似性
我们可以将一个句子表示为一个单词数组，例如，句子 "I am happy with leetcode" 可以表示为 arr = ["I","am",happy","with","leetcode"]
给定两个句子 sentence1 和 sentence2 分别表示为一个字符串数组，并给定一个字符串对 similarPairs ，其中 similarPairs[i] = [xi, yi] 表示两个单词 xi and yi 是相似的。
如果 sentence1 和 sentence2 相似则返回 true ，如果不相似则返回 false 。
两个句子是相似的，如果:
sentence1[i] 和 sentence2[i] 是相似的请注意，一个词总是与它自己相似，也请注意，相似关系是不可传递的。例如，如果单词 a 和 b 是相似的，单词 b 和 c 也是相似的，那么 a 和 c 不一定相似 。
示例 1:
输入: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]] 输出: true 解释: 这两个句子长度相同，每个单词都相似。
示例 2:
输入: sentence1 = ["great"], sentence2 = ["great"], similarPairs = [] 输出: true 解释: 一个单词和它本身相似。
示例 3:
输入: sentence1 = ["great"], sentence2 = ["doubleplus","good"], similarPairs = [["great","doubleplus"]] 输出: false 解释: 因为它们长度不同，所以返回false。
提示:
1 <= sentence1.length, sentence2.length <= 10001 <= sentence1[i].length, sentence2[i].length <= 20sentence1[i] 和 sentence2[i] 只包含大小写英文字母0 <= similarPairs.length <= 2000similarPairs[i].length == 21 <= xi.length, yi.length <= 20(xi, yi) 都是 不同 的原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 41.8 MB, 提交时间: 2023-10-15 19:34:00
class Solution {
public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
if (sentence1.length != sentence2.length) {
return false;
}
Map<String, Set<String>> m1 = new HashMap<>();
Map<String, Set<String>> m2 = new HashMap<>();
for (List<String> pair : similarPairs) {
Set<String> set1 = m1.getOrDefault(pair.get(0), new HashSet<>());
set1.add(pair.get(1));
m1.put(pair.get(0), set1);
Set<String> set2 = m2.getOrDefault(pair.get(1), new HashSet<>());
set2.add(pair.get(0));
m2.put(pair.get(1), set2);
}
for (int i = 0; i < sentence1.length; i++) {
String s1 = sentence1[i];
String s2 = sentence2[i];
if (!s1.equals(s2) && !m1.getOrDefault(s1, new HashSet<>()).contains(s2)
&& !m2.getOrDefault(s1, new HashSet<>()).contains(s2)) {
return false;
}
}
return true;
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 11.5 MB, 提交时间: 2023-10-15 19:33:20
class Solution {
public:
bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
if (sentence1.size() != sentence2.size()) return false;
unordered_map<string_view, unordered_set<string_view>> dict;
for (auto& v : similarPairs) {
dict[v[0]].emplace(v[1]);
}
return equal(sentence1.cbegin(), sentence1.cend(), sentence2.cbegin(), [&dict](auto& a, auto& b) {
return a == b || (dict.count(a) && dict[a].count(b)) || (dict.count(b) && dict[b].count(a)); });
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-10-15 19:31:15
class Solution:
def areSentencesSimilar(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
if len(words1) != len(words2): return False
pairset = set(map(tuple, pairs))
return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset
for w1, w2 in zip(words1, words2))