[每日 LeetCode] 893. Groups of Special-Equivalent Strings

原文链接 [每日 LeetCode] 893. Groups of Special-Equivalent Strings

Description:

You are given an array A of strings.

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

A 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
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

思路：本题题意为求字符串数组中特殊的相等字符串，只读一遍题目发现有点绕，多读几遍就好了。题目要求找出字符串数组中存在的特殊相等字符对，特殊性体现在字符对中的每个字符串需要奇数和偶数位置上的字符相同（不考虑顺序）。解决方案可以分别记录某个字符串中奇数位和偶数位上的字符串，然后对两个字符串排序并使用 pair 结构判断保证记录的唯一性。如原字符串: "abcdefggyy"，其奇数串 : "acegy"，偶数串 : "bdfgy"，然后使用嵌入 map 记录符合符合条件的字符串有多少组。

C++ 代码

class Solution {
public:
    int numSpecialEquivGroups(vector<string>& A) {
        map<std::pair<string,string>,int> mymap; // key:pattern pair
        for(int i = 0 ; i < A.size() ; i++){
            string s[2];
            for(int j = 0 ; j < A[i].length() ; j++)
                s[j%2]+= A[i][j];
            sort(s[0].begin(),s[0].end()),sort(s[1].begin(),s[1].end());
            mymap[{s[0],s[1]}]++;
        }
        return mymap.size();       
    }
};

运行时间：12ms

运行内存：10.1M