本文共 3369 字，大约阅读时间需要 11 分钟。

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}.  Notice that "tars" and "arts" are in the same group even though they are not similar.  Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of strings.  Every string in A is an anagram of every other string in A.  How many groups are there?

Example 1:

Input: A = ["tars","rats","arts","star"]Output: 2

Constraints:

• 1 <= A.length <= 2000
• 1 <= A[i].length <= 1000
• A.length * A[i].length <= 20000
• All words in A consist of lowercase letters only.
• All words in A have the same length and are anagrams of each other.
• The judging time limit has been increased for this question.

Accepted

15,146

Submissions

41,209

---------------------------------------------------------------------------------------------

几个注意点：

1. 用并查集数有几组，最多需要两两都比较一遍。例如A和B一组，A和C一组，那么B和C一组。但是对于这题来说，A和B不相似，A和C相似，B和C相似，那么A和B也一组，所以两两比较逃不掉。最多能避免的情况就是A和B相似，A和C相似，那么B和C肯定一组不用判断了。但是这也取决于B,C提前在一组的可能性，实测并没有变快
2. 对于Python这种慢语言，这题必须两种角度考虑：直接比、neighbor+字典
3. 对于Python这种慢语言，长度为w的字符串，求一个neighbor的复杂度是O(w)，全部Neighbor就是O(w^3)，所以比较的时候要注意

最后是codes：

class Solution:    def isSimilar(self, s1, s2):        diff, l = 0, len(s1)        for i in range(l):            if (s1[i] != s2[i]):                diff += 1                if (diff > 2):                    return False        return True    def find(self, f, x):        return f[x] if x == f[x] else self.find(f, f[x])    def merge(self, f, x, y):        rx = self.find(f, f[x])        ry = self.find(f, f[y])        f[ry] = rx    def numSimilarGroups(self, A):        A = list(set(A))        l,w = len(A), len(A[0])        res = 0        f = [i for i in range(l)]        if l <= w*w:            for i in range(l):                for j in range(i + 1, l):                    if (self.find(f, i) != self.find(f,j)):                        isSimilar = self.isSimilar(A[i], A[j])                        if (isSimilar):                            self.merge(f, i, j)        else:            dict = {}            for i in range(l):                if (A[i] in dict):                    dict[A[i]].add(i)                else:                    dict[A[i]] = {i}                word = list(A[i])                for i0 in range(w):                    for j0 in range(i0+1, w):                        if (word[i0] != word[j0]):                            word[i0],word[j0] = word[j0],word[i0]                            neighbor = ''.join(word)                            if (neighbor in dict):                                dict[neighbor].add(i)                            else:                                dict[neighbor] = {i}                            word[i0],word[j0] = word[j0],word[i0]            for i in range(l):                for j in dict[A[i]]:                    self.merge(f,i,j)        for i in range(l):            if (i == f[i]):                res += 1        return ress = Solution()print(s.numSimilarGroups(["tars","rats","arts","star"]))

转载地址：http://ptfoi.baihongyu.com/