Leetcode 839 Similar String Groups

发表于 |


分析：
在A中所有字符串都是由相同的字符组成的，但顺序不一样，如果两个字符串只有两个字符位置不同，那么我们把这两个字符串归为一组，求共有多少组。
注意：len(A)*len(A[i]) < 20000,保证了n^2*m或者m^2*n的复杂度是可行的

思路：
这是一道典型的union find题，是在prim算法还是在kruskal算法中这个思想被用到了。这里我介绍两种方法，一种是union find，一种是dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution(object):
    def numSimilarGroups(self, A):
        """
        :type A: List[str]
        :rtype: int
        """
        # 判断两个字符串是否是一个组
        def isSimilar(s1,s2):
            cnt = 0
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    cnt += 1
                    if cnt > 2: return False
            return True

        # 标准的union find思路，也就是将所有在一个组内字符串用同一个字符串记录
        # 如 arts:arts, rats: arts, tars: arts, star: star
        d = {u:u for u in A}
        def find(u):
            if u != d[u]:
                d[u] = find(d[u])
            return d[u]

        #设初始组数为n，每找到一个该在同一组的总组数就减1
        self.n = len(A)
        def union(x,y):
            x,y = find(x),find(y)
            if x != y:
                d[y] = x
                self.n -= 1
                return True
            return False

        for x in range(len(A)):
            for y in range(x+1,len(A)):
                if isSimilar(A[x],A[y]): 
                    union(A[x],A[y])
        return self.n

O(m*n^2) time 其中n为A的长度，m为A[i]的长度

再介绍一种dfs方法，我们把每个字符串看做一个节点，如果两个字符串是同一个组则将它们相连接，最后构成一个图，在这个图中用dfs方法找有多少个连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
    def numSimilarGroups(self, A):
        """
        :type A: List[str]
        :rtype: int
        """
        Graph = collections.defaultdict(list)
        # 判断两个字符串是否是在一个组
        def isSimilar(x,y):
            res = 0
            for i in range(len(x)):
                if x[i] != y[i]:
                    res += 1
                    if res > 2: return False
            return res == 2

        # 构建图，O(m*n^2) time
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                if isSimilar(A[i],A[j]):
                    Graph[i].append(j)
                    Graph[j].append(i)

        # 用一个数组判断节点是否已被访问
        visited = [0] * len(A)
        def dfs(u):
            visited[u] = 1
            for v in Graph[u]:
                if visited[v]: continue
                dfs(v)

        res = 0
        for i in range(len(A)):
            if visited[i]: continue
            # 一次dfs得到一个连通分量
            dfs(i)
            res += 1
        return res

这道题还挺可惜的，这两种方法用python写都tle了，但是用java,c++都完全ok，就学下思路吧~