文章目錄

• • 1. 題目
  • 2. 解題

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

---

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

總結

以上是生活随笔為你收集整理的LeetCode 734. 句子相似性（哈希）的全部內容，希望文章能夠幫你解決所遇到的問題。

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