题目描述

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

如果经过任意次数的移动，使得 S == T，那么两个字符串 S 和 T 是特殊等价的。

一次移动 包括选择两个索引 i 和 j，且 i％2 == j％2，并且交换 S[i] 和 S[j]。

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

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

样例

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

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

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

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

注意

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

算法

(哈希表) $O(n m \log m)$

1. 枚举每一个字符串，然后将字符串的偶数位子串和奇数位子串取出来，分别排序，然后再拼接起来。
2. 如果之前没有出现过拼接后的字符串，则增加答案，并放入哈希表。

时间复杂度

• 共需要枚举 $n$ 个字符串，每个字符串需要 $O(m \log m)$ 的时间排序和拼接，故总时间复杂度为 $O(nm \log m)$。

空间复杂度

• 需要一个哈希表，最坏情况需要存放所有字符串，故空间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    int numSpecialEquivGroups(vector<string>& A) {
        int m = A[0].length();
        unordered_set<string> vis;
        int ans = 0;

        for (auto str : A) {
            string even, odd;
            for (int j = 0; j < m; j += 2)
                even += str[j];
            for (int j = 1; j < m; j += 2)
                odd += str[j];

            sort(even.begin(), even.end());
            sort(odd.begin(), odd.end());

            string fin = even + odd;
            if (vis.find(fin) == vis.end()) {
                vis.insert(fin);
                ans++;
            }
        }
        return ans;
    }
};