[LeetCode]Sentence Similarity

这道题similarity不是传递的，我们只要在hash map中建立对应的关系即可，注意一个字符可能有多个映射。时间复杂度O(N)，空间复杂度O(N)，代码如下:

	class Solution {
	public:
	bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
	unordered_map<string, unordered_set<string>> map;
	for (auto& p : pairs)
	{
	map[p.first].insert(p.second);
	map[p.second].insert(p.first);
	}
	if (words1.size() != words2.size())return false;
	int len = words1.size();
	for (int i = 0; i < len; ++i)
	{
	string word1 = words1[i], word2 = words2[i];
	if (word1 != word2 && map[word1].find(word2) == map[word1].end())
	return false;
	}
	return true;
	}
	};

view raw Sentence Similarity.cpp hosted with ❤ by GitHub