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.

move  consists of choosing two indices i and jwith i % 2 == j % 2, and swapping S[i] with S[j].

Now, a  group of special-equivalent strings fromA  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 <= A.length <= 1000
• 1 <= A[i].length <= 20
• All A[i] have the same length.
• All A[i] consist of only lowercase letters.

class Solution {
public:
int numSpecialEquivGroups(vector<string>& A) {
unordered_set<string> st;
for (string word : A) {
string even, odd;
for (int i = 0; i < word.size(); ++i) {
if (i % 2 == 0) even += word[i];
else odd += word[i];
}
sort(even.begin(), even.end());
sort(odd.begin(), odd.end());
st.insert(even + odd);
}
return st.size();
}
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/893

https://leetcode.com/problems/groups-of-special-equivalent-strings/

https://leetcode.com/problems/groups-of-special-equivalent-strings/discuss/163413/Java-Concise-Set-Solution

https://leetcode.com/problems/groups-of-special-equivalent-strings/discuss/163412/C%2B%2B-Simple-Solution

https://leetcode.com/problems/groups-of-special-equivalent-strings/discuss/163891/C%2B%2B-Create-a-signature-for-each-string

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation