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.

这道题定义了一种特殊相等的关系,就是说对于一个字符串,假如其偶数位字符之间可以互相交换,且其奇数位字符之间可以互相交换,交换后若能跟另一个字符串相等,则这两个字符串是特殊相等的关系。现在给了我们一个字符串数组,将所有特殊相等的字符串放到一个群组中,问最终能有几个不同的群组。最开始的时候博主没仔细审题,以为是随意交换字母,就直接对每个单词进行排序,然后扔到一个 HashSet 中就行了。后来发现只能是奇偶位上互相交换,于是只能现先将奇偶位上的字母分别抽离出来,然后再进行分别排序,之后再合并起来组成一个新的字符串,再丢到 HashSet 中即可,利用 HashSet 的自动去重复功能,这样最终留下来的就是不同的群组了,参见代码如下:

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

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation