[LeetCode]Sentence Similarity II

这道题和Sentence Similarity是类似的，唯一的区别是similarity是传递的。所以这道题我们要建图，然后找所有的connected component，这里有两种方法，第一种是dfs，时间空间复杂度均为O(N + M)，N为节点数，M为边数，代码如下：

	class Solution {
	public:
	bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
	if (words1.size() != words2.size())return false;
	int cnt = 0;
	unordered_map<string, int> id;
	for (auto& pair : pairs)
	{
	string str1 = pair.first, str2 = pair.second;
	if (id.find(str1) == id.end())
	id[str1] = cnt++;
	if (id.find(str2) == id.end())
	id[str2] = cnt++;
	}
	int n = id.size();
	vector<vector<int>> graph(n);
	for (auto& pair : pairs)
	{
	int u = id[pair.first], v = id[pair.second];
	graph[u].push_back(v);
	graph[v].push_back(u);
	}
	unordered_map<int, int> group;
	cnt = 0;
	for (int i = 0; i < n; ++i)
	{
	if (group.find(i) == group.end())
	dfs(graph, i, group, cnt++);
	}
	int len = words1.size();
	for (int i = 0; i < len; ++i)
	{
	string word1 = words1[i], word2 = words2[i];
	if ((id.find(word1) == id.end() || id.find(word2) == id.end()) && word1 != word2)return false;
	if (word1 != word2 && group[id[word1]] != group[id[word2]])return false;
	}
	return true;
	}
	private:
	void dfs(vector<vector<int>>& graph, int curr, unordered_map<int, int>& group, int id)
	{
	if (group.find(curr) != group.end())return;
	group[curr] = id;
	for (auto& adj : graph[curr])
	dfs(graph, adj, group, id);
	}
	};

view raw Sentence Similarity II_dfs.cpp hosted with ❤ by GitHub

Union Find也可以用来解决图的连接性的问题，具体可以参考链接的文章。时间空间复杂度均为O(N + M)，N为节点数，M为边数，代码如下：

	class UnionFind
	{
	public:
	UnionFind(int n)
	{
	parent = vector<int>(n, 0);
	size = vector<int>(n, 1);
	for (int i = 0; i < n; ++i)parent[i] = i;
	}
	void connect(int i, int j)
	{
	int rootI = root(i), rootJ = root(j);
	if (size[rootI] >= size[rootJ])
	{
	parent[rootJ] = rootI;
	size[rootI] += size[rootJ];
	}
	else
	{
	parent[rootI] = rootJ;
	size[rootJ] += size[rootI];
	}
	}
	bool find(int i, int j)
	{
	return root(i) == root(j);
	}
	private:
	vector<int> parent, size;
	int root(int i)
	{
	if (parent[i] == i)return i;
	int res = root(parent[i]);
	parent[i] = res;
	return res;
	}
	};
	class Solution {
	public:
	bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
	if (words1.size() != words2.size())return false;
	int cnt = 0;
	unordered_map<string, int> id;
	for (auto& pair : pairs)
	{
	string str1 = pair.first, str2 = pair.second;
	if (id.find(str1) == id.end())
	id[str1] = cnt++;
	if (id.find(str2) == id.end())
	id[str2] = cnt++;
	}
	int n = id.size();
	UnionFind uf(n);
	for (auto& pair : pairs)
	{
	int u = id[pair.first], v = id[pair.second];
	uf.connect(u, v);
	}
	int len = words1.size();
	for (int i = 0; i < len; ++i)
	{
	string word1 = words1[i], word2 = words2[i];
	if ((id.find(word1) == id.end() || id.find(word2) == id.end()) && word1 != word2)return false;
	if (word1 != word2 && !uf.find(id[word1], id[word2]))return false;
	}
	return true;
	}
	};

view raw Sentence Similarity II__union_find.cpp hosted with ❤ by GitHub