特殊等价字符串组

今天药忘吃喽~ 2021-11-09 00:38 270阅读 0赞

记录一下一道有意思的题目：来源：[https://leetcode-cn.com/problems/groups-of-special-equivalent-strings/][https_leetcode-cn.com_problems_groups-of-special-equivalent-strings]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjQ3NTQ0_size_16_color_FFFFFF_t_70][]

这个题目的意思通俗点说就是一个字符串的奇数位上的字符可以相互替换，偶数位上的字符也可以相互替换。但是奇数位和偶数位的不能换，这样换任意次后两个字符串相同的话就是同一组的，然后要求出现在一共有多少组。

**思路：**

**将一个字符串的奇数位的字符和偶数位的字符分别提取出来组成两个新的字符串，然后进行内部排序，再组合成一个字符串，这样一个组的结果肯定是相同的，然后设置一个set，将结果保存到set中，因为set中是自动去重的，不会存在重复的元素，所以最后返回set中的元素的数量就可以了。**

**代码：**

class Solution {
    public:
        int numSpecialEquivGroups(vector<string>& A) {
            set<vector<char>> res;
            for(int i=0;i<A.size();i++)
            {
                vector<char> temp1;
                vector<char> temp2;
                vector<char> vec3;
                for(int j=0;j<A[i].length();j++)
                {
                    if(j%2==0)
                        temp1.push_back(A[i].at(j));
                    else
                        temp2.push_back(A[i].at(j));
                }
                sort(temp1.begin(),temp1.end());
                sort(temp2.begin(),temp2.end());
                vec3.insert(vec3.end(),temp1.begin(),temp1.end());
    		    vec3.insert(vec3.end(),temp2.begin(),temp2.end());
                res.insert(vec3);
                
            }
            return res.size();
        }
    };

[https_leetcode-cn.com_problems_groups-of-special-equivalent-strings]: https://leetcode-cn.com/problems/groups-of-special-equivalent-strings/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjQ3NTQ0_size_16_color_FFFFFF_t_70]: /images/20211108/b385a79cdfab4c4bbdec4b6526241daf.png