# 原题

You are given an array `A` of strings.

Two strings `S` and `T` are special-equivalent if after any number of moves, S == T.

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
```

Note:

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

# 代码

[code lang=”cpp”]
class Solution {
public:
int numSpecialEquivGroups(vector<string>& A) {
map<string, int> a;
string es, os;
for (auto str : A) {
es = os = "";
for (int i = 0; i < str.length(); ++i) {
if (i % 2 == 0) es += str[i];
if (i % 2 == 1) os += str[i];
}
sort(es.begin(), es.end());
sort(os.begin(), os.end());
a[es + os] += 1;
}
return a.size();
}
};
[/code]

# 复杂度

M 代表数组A的长度
N 代表A数组中最长的字符串的长度

Share: