讨论社区

839. 相似字符串组,现有数据python似乎过不了了。

该题数据太大,python性能低,目前给的时间无法通过,无论我自己的代码还是,Weekly Contest 85 国际第20名lbjlc  的代码现在都无法通过这题的所有数据了(排名靠前的只有他的代码是python),大约只能通过一半的数据,85周赛国际赛绝大多数通过这道题的人都没有使用python,可以提供的参考代码很少,但即使是完全一样的算法,把其他语言翻译成python也无法通过,反正评论和题解里面的非python代码翻译python应该都是过不了,官方是否应该再调整下数据或python的通过时间。


以下两个代码都无法通过全部数据,我的代码最多过31-34个数据左右,匹配加并查集,大神lbjlc 的代码也差不太多,也是匹配加深搜,测了一次是30这样,用例应该是比起刚出这题的时候扩了数据,但python的时间实在是跟不上啊。


```

我的代码:

class Solution:

    def numSimilarGroups(self, A: List[str]) -> int:

        A = [*{*A}]

        n, m = len(A), len(A[0])

        def check(x, y):

            t = 0

            for i in range(m):

                if x[i] != y[i]:

                    t += 1

                    if t > 2:

                        return False

            return t == 2

        p = {i :{i} for i in range(n)}

        for i in range(n):

            for j in range(i + 1, n):

                if p[i] is not p[j]:

                    if check(A[i], A[j]):

                        p[i] |= p[j]

                        for k in p[j]:

                            p[k] = p[i]

        ans = {id(p[i]) for i in p}

        return len(ans)

```

周赛国际排名20 lbjlc 的代码:

```

class Solution(object):

    def numSimilarGroups(self, A):

        n = len(A)

        m = len(A[1])

        

        

        collect = dict()

        graph = [set() for i in range(n)]

        

        def similar(s1, s2):

            i, j = -1, -1

            for k in range(len(s1)):

                if s1[k] != s2[k]:

                    if i == -1:

                        i = k

                    elif j == -1:

                        j = k

                        if s1[i] != s2[j] or s1[j] != s2[i]:

                            return False

                    else:

                        return False

            return True

        

        for i in range(n):

            for j in range(i + 1, n):

                if similar(A[i], A[j]):

                    graph[i].add(j)

                    graph[j].add(i)

        

        visited = [0] * n

        res = 0

        def dfs(i, visited, n, graph):

            if visited[i]:

                return

            visited[i] = 1

            for j in graph[i]:

                dfs(j, visited, n, graph)

            return

        for i in range(n):

            if not visited[i]:

                res += 1

                dfs(i, visited, n, graph)

        return res

        

        """

        :type A: List[str]

        :rtype: int

        """

```


0 人关注了该问题 关注

0

feiceh • 3月前

题目相关问题力扣产品技术团队会持续进行维护和优化,感谢您的支持~

0 个讨论

您需要登录后才可回复
您需要登录后才可以回复