Leetcode 893 Groups of Special-Equivalent Strings

发表于 |

You are given an array A of strings.
Two strings S and T are special-equivalent if after any number of moves, S == T.
A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].
Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.
Return the number of groups of special-equivalent strings from A.

Example 1:
Input: [“a”,”b”,”c”,”a”,”c”,”c”]
Output: 3
Explanation: 3 groups [“a”,”a”], [“b”], [“c”,”c”,”c”]

Example 2:
Input: [“aa”,”bb”,”ab”,”ba”]
Output: 4
Explanation: 4 groups [“aa”], [“bb”], [“ab”], [“ba”]

Example 3:
Input: [“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
Output: 3
Explanation: 3 groups [“abc”,”cba”], [“acb”,”bca”], [“bac”,”cab”]

Example 4:
Input: [“abcd”,”cdab”,”adcb”,”cbad”]
Output: 1
Explanation: 1 group [“abcd”,”cdab”,”adcb”,”cbad”]

Note:

  1. 1 <= A.length <= 1000
  2. 1 <= A[i].length <= 20
  3. All A[i] have the same length.
  4. All A[i] consist of only lowercase letters.

分析：

  1. 觉不觉得有点像union find，找“同源”的所有元素将其归为一组，最后看有多少组
  2. 我们如何判断两个字符串是否“相同”呢，根据题目要求，奇数位可以和奇数位交换位置，偶数位可以和偶数位交换位置，那么我们自然想到，只要两个字符串分别在奇数位上和偶数位上的字符组成都相同即可，在这即可分两种思路：
    1. 使用Counter函数可快速获得，一共26个字母，所以比较两个Counter非常快速，例如’abcd’和’cdab’：
      1. ‘abcd’：奇数位：{‘a’:1,’c’:1},偶数位：{‘b’:1,’d’:1}
      2. ‘cdab’：奇数位：{‘a’:1,’c’:1},偶数位：{‘b’:1,’d’:1}
      3. 故两者相同
    2. 将字符串先排序再比较，因为每个A[i]长度不超过20，所以实际这个可以更快

思路1（针对Counter方法）：

  1. 我们先默认所有的元素都不“同源”，则应该有len(A)个不同的组
  2. 每次我们遍历到一个字符串，将其和前面所有的字符串进行对比，如果出现同源则将总数减一，且终止比较（否则可能多减，如例4）（虽然实际上我是用的visited来模仿union find的思路）

思路2（针对sort方法）：

  1. 直接将排序好的字符串作为key值，最后判断有多少种不同的key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 思路1,O(m*n^2),n=len(A), m=len(A[i])
class Solution(object):
    def numSpecialEquivGroups(self, A):
        """
        :type A: List[str]
        :rtype: int
        """
        d = {s:{} for s in A}
        for s in A:
            d[s][0] = collections.Counter(s[::2])
            d[s][1] = collections.Counter(s[1::2])
        res = len(A)
        visited = set()
        for i in range(len(A)):
            for j in range(i):
                if d[A[i]] == d[A[j]] and j not in visited:
                    visited.add(j)#同源之后就将其删除，只保留最初的那一个
                    res -= 1
        return res

34 / 34 test cases passed.
difficulty: easy
Runtime: 384 ms
1
2
3
4
5
6
7
8
9
10
11
12
13
#思路2,O(n*mlogm),n=len(A), m=len(A[i])
class Solution:
    def numSpecialEquivGroups(self, A):
        d = collections.defaultdict(int)
        for s in A:
            s1 = ''.join(sorted(s[::2]))
            s2 = ''.join(sorted(s[1::2]))
            d[(s1, s2)] += 1
        return len(d)

34 / 34 test cases passed.
difficulty: easy
Runtime: 40 ms