893. Groups of Special-Equivalent Strings*

2022-05-30 10:33:23

893. Groups of Special-Equivalent Strings*

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

題目描述

You are given an array

of strings.

A move onto

consists of swapping any two even indexed characters of

, or any two odd indexed characters of

Two strings

and

are special-equivalent if after any number of moves onto

For example,

S = "zzxy"

and

T = "xyzz"

are special-equivalent because we may make the moves

"zzxy" -> "xzzy" -> "xyzz"

that swap

S[0]

and

S[2]

, then

S[1]

and

S[3]

Now, a group of special-equivalent strings from

is a non-empty subset of

such that:

Every pair of strings in the group are special equivalent, and;
The group is the largest size possible (ie., there isn’t a string S not in the group such that S
is special equivalent to every string in the group)

Return the number of groups of special-equivalent strings from
A .

Example 1:

Input: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3
Explanation: 
One group is ["abcd", "cdab", "cbad"], since they are all pairwise special equivalent, and none of the other strings are all pairwise special equivalent to these.

The other two groups are ["xyzz", "zzxy"] and ["zzyx"].  Note that in particular, "zzxy" is not special equivalent to "zzyx".

Example 2:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3

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.

C++ 實作 1

參考: C++ Simple Solution, 作者的想法是:

General Idea:

Split strings in two to substrings, 1 with even indexed characters, and 1 with odd

Sort the two substrings (We do this because if you can swap on string with another, when sorted they will equal each other because they must have the same characters)

Insert your pair of strings into set, this will keep track of the unique “groups”

Rerturn the size of your set

class Solution {
public:
    int numSpecialEquivGroups(vector<string>& A) {
        set<pair<string, string>> record;
        for (auto &w : A) {
            pair<string, string> p;
            for (int i = 0; i < w.size(); ++ i) {
                if (i % 2 == 0) p.first += w[i];
                else p.second += w[i];
            }
            std::sort(p.first.begin(), p.first.end());
            std::sort(p.second.begin(), p.second.end());
            record.insert(p);
        }
        return record.size();
    }
};

893. Groups of Special-Equivalent Strings*