[LeetCode]Similar String Groups

仍然是图的问题，每一个string就是一个节点，如果可以通过交换一对字符从字符串a变到b，那么这两个字符串对应的节点就有一条无向边相连。我们构建好图之后DFS找有多少connected component即可。建图我们有两个思路：

1. 对于每一个string s 对应的节点，我们遍历所有交换的可能，然后看交换后的string s'是否是图中的一个节点，是的话我们把s和s'连上一条边
2. 对于输入数组的每一个string，我们check其和之前所有的string之间是否有边连接，每一次这样的check我们需要遍历整个字符串

假设数组长度为N，每个字符串长度为M。第一种方法的时间复杂度为O(N * M^2)，第二种法法的时间复杂度为O(N^2 * M), 具体谁快取决于M和N的值。我们的解法采取第二种建图的方法。图建好后DFS或者并查集找connected component即可，我们采用DFS的解法，总的时间复杂度仍然是取决于建图的复杂度，代码如下：

	class Solution {
	public:
	int numSimilarGroups(vector<string>& A) {
	int n = A.size();
	vector<vector<int>> g(n);
	for(int i = 1; i < n; ++i)
	{
	for(int j = 0; j < i; ++j)
	{
	if(isAdj(A[j], A[i]))
	{
	g[i].push_back(j);
	g[j].push_back(i);
	}
	}
	}
	int res = 0;
	vector<bool> visited(n, false);
	for(int i = 0; i < n; ++i)
	{
	if(!visited[i])
	{
	dfs(g, visited, -1, i);
	++res;
	}
	}
	return res;
	}
	private:
	bool isAdj(string u, string v)
	{
	int len = u.size(), cnt = 0;
	for(int i = 0; i < len; ++i)
	{
	if(u[i] != v[i])
	if(++cnt > 2)
	return false;
	}
	return true;
	}
	void dfs(vector<vector<int>>& g, vector<bool>& visited, int from, int to)
	{
	if(visited[to])return;
	visited[to] = true;
	for(const auto& adj : g[to])
	{
	if(adj != from)
	dfs(g, visited, to, adj);
	}
	}
	};

view raw Similar String Groups.cpp hosted with ❤ by GitHub