跳转至

LeetCode: 893. 特殊等价字符串组

1、题目描述

你将得到一个字符串数组 A

如果经过任意次数的移动,S == T,那么两个字符串 ST 是*特殊等价*的。

一次*移动*包括选择两个索引 ij,且 i%2 == j%2,并且交换 S[j]S [i]

现在规定,*A 中的特殊等价字符串组*是 A 的非空子集 S,这样不在 S 中的任何字符串与 S 中的任何字符串都不是特殊等价的。

返回 A 中特殊等价字符串组的数量。

示例 1:

输入:["a","b","c","a","c","c"]
输出:3
解释:3 组 ["a","a"],["b"],["c","c","c"]

示例 2:

输入:["aa","bb","ab","ba"]
输出:4
解释:4 组 ["aa"],["bb"],["ab"],["ba"]

示例 3:

输入:["abc","acb","bac","bca","cab","cba"]
输出:3
解释:3 组 ["abc","cba"],["acb","bca"],["bac","cab"]

示例 4:

输入:["abcd","cdab","adcb","cbad"]
输出:1
解释:1 组 ["abcd","cdab","adcb","cbad"]

提示:

  • 1 <= A.length <= 1000
  • 1 <= A[i].length <= 20
  • 所有 A[i] 都具有相同的长度。
  • 所有 A[i] 都只由小写字母组成。

2、解题思路

一开始对题意没怎么理解,理解了以后,就很简单了
  • 将字符串数组进行分类,满足下面两个条件的分在一组
  • 两个字符串,经过任意次的字符移动,等价
  • 移动的字符的下标索引,ij,且 i%2 == j%2

根据上面的描述,我们就明白了,如果两个字符串能够分到一组,首先字符肯定是一样的,长度一样,而且奇数位置所有字符是相同的,偶数位置所有字符是相同的,于是,我们就利用这个性质,进行分组

  • 找出当前字符串奇数位置,偶数位置的字符,排序,作为字典的键
class Solution:
    def numSpecialEquivGroups(self, A):
        """
        :type A: List[str]
        :rtype: int
        """
        ans_dict = collections.defaultdict(list)

        for s in A:
            even = "".join(sorted([c for index, c in enumerate(s) if index % 2 == 0]))
            odd = "".join(sorted([c for index, c in enumerate(s) if index % 2 == 1]))

            ans_dict[even + odd].append(s)
        return len(ans_dict)