[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的解法，总的时间复杂度仍然是取决于建图的复杂度，代码如下：