CTF of Z2BNS
0%

特殊等价字符串组

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目地址

难度：⭐

题目描述：

你将得到一个字符串数组 A。

每次移动都可以交换 S 的任意两个偶数下标的字符或任意两个奇数下标的字符。

如果经过任意次数的移动，S == T，那么两个字符串 S 和 T 是 特殊等价 的。

例如，S = "zzxy" 和 T = "xyzz" 是一对特殊等价字符串，因为可以先交换 S[0] 和 S[2]，然后交换 S[1] 和 S[3]，使得 "zzxy" -> "xzzy" -> "xyzz" 。

现在规定，A 的 一组特殊等价字符串 就是 A 的一个同时满足下述条件的非空子集：

  1. 该组中的每一对字符串都是 特殊等价 的
  2. 该组字符串已经涵盖了该类别中的所有特殊等价字符串，容量达到理论上的最大值（也就是说，如果一个字符串不在该组中，那么这个字符串就 不会 与该组内任何字符串特殊等价）
    返回 A 中特殊等价字符串组的数量。

示例1：

1
2
3
4
5
输入：["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
输出：3
解释：
其中一组为 ["abcd", "cdab", "cbad"]，因为它们是成对的特殊等价字符串，且没有其他字符串与这些字符串特殊等价。
另外两组分别是 ["xyzz", "zzxy"] 和 ["zzyx"]。特别需要注意的是，"zzxy" 不与 "zzyx" 特殊等价。

示例2：

1
2
3
输入：["abc","acb","bac","bca","cab","cba"]
输出：3
解释：3 组 ["abc","cba"]，["acb","bca"]，["bac","cab"]

提示：

  • 1 <= A.length <= 1000
  • 1 <= A[i].length <= 20
  • 所有 A[i] 都具有相同的长度。
  • 所有 A[i] 都只由小写字母组成。
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

读完题目后觉得这道题还挺难的，就在脑子里多想一想，还是被我想到了，哈哈哈😁

要求字符串数组A中特殊等价字符串组的数量，注意到一组特殊等价字符串是交换偶数下标字符和奇数下标字符得到的，那么他们都可以转换成同一个字符串，只要对数组A中的每个字符串分别按奇数下标、偶数下标排序，然后再求它们找那个不同字符串的数量就好了，最后一步可以利用set集合无序不可重复的特性。现在就变成怎么把字符串分别按照奇数下标和偶数下标排序。

sort()函数好像没有步长，不能自定义排序规则，所以需要自己实现了，对字符串考虑把偶数位置的元素放在前面，奇数位置的元素放在后面，然后调用sort函数对前半部分和后半部分分别排序，排序后的字符串就是特殊等价字符串，放入set集合中，最后返回set集合的长度（一组特殊等价字符串只存储了一个，所以长度就是特殊等价字符串组的数量）。

也可以分别把字符串中的偶数位置、奇数位置字符提取出来然后排序最后拼接放入到set集合中。

c++代码：(执行用时12ms，击败95.61%，内存消耗8.7M，击败35.84%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int numSpecialEquivGroups(vector<string>& A) {
        int result=0;
        int n=A[0].length();
        //set集合无序不可重复,存储A的特殊等价字符串
        set<string> equal_s;
        for(string s:A){
            //双指针排序
            //前半部分索引i表示，后半部分索引tmp，把前半部分奇数下标位置和后半部分偶数下标部分交换
            int tmp=(n+1)/2;
            //若后半部分开始索引是奇数，则tmp加1得到开始的偶数下标
            if(tmp%2==1){
                ++tmp;
            }
            for(int i=1;i<(n+1)/2;i+=2){
                //奇偶位置分别排序，偶数位置元素在前
                swap(s[i],s[tmp]);
                tmp+=2;
            }
            //对前半部分（偶数位置元素）排序
            sort(s.begin(),s.begin()+(n+1)/2);
            //对后半部分（奇数位置元素）排序
            sort(s.begin()+(n+1)/2,s.end());
            equal_s.insert(s);
        }
        return equal_s.size();
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法：计数

思路和算法

让我们试着表述一个特殊等价的字符串 $S$，通过找到函数 $\mathcal{C}$ 使得 $S \equiv T \iff \mathcal{C}(S) = \mathcal{C}(T)$。

通过交换，我们可以排列偶数索引字母和奇数索引字母。这些排列的特征在于字母的数量：所有这样的排列都有相同的数量，不同的数量会产生不同的排列。

因此，函数 $\mathcal{C}(S) =$（S 中偶数索引字母的数量，其后是 S 中奇数索引字母的数量）成功地刻画了这一等价关系。

然后，我们统计出满足 $S \in A$ 的 $\mathcal{C}(S)$ 的数量。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numSpecialEquivGroups(String[] A) {
        Set<String> seen = new HashSet();
        for (String S: A) {
            int[] count = new int[52];
            for (int i = 0; i < S.length(); ++i)
                count[S.charAt(i) - 'a' + 26 * (i % 2)]++;
            seen.add(Arrays.toString(count));
        }
        return seen.size();
    }
}

复杂度分析

  • 时间复杂度：$O(\sum\limits_{i} (A_i)\text{.length})$。

  • 空间复杂度：$O(N)$，其中 $N$ 是 A 的长度。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解虽然和我的思路不太一样，但本质是一样的都是找到一组等价字符串的等价关系，然后转换成一致的最后统计数量。等价字符串是通过交换偶数下标字符或奇数下标字符得到的，我是采用了一组等价字符串中的每个字符串必然可以通过排序转换成一个相同的字符串形式，也就是奇数下标、偶数下标字符分别排序，以下列输入为例：

1
2
输入：["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
输出：3

每个字符串通过排序可以转换成如下：

1
2
3
4
5
6
7
8
9
10
11
“abcd”=》“acbd”

“cdab”=》“acbd”

“cbad”=》“acbd”

“xyzz”=》“xzyz”

“zzxy”=》“xzyz”

“zzyx“=》”yzxz“

根据转换后的结果可以看到前三个字符串相同是一组特殊等价字符串、中间两个一组、最后一个一组所以特殊等价字符串的数量为3，即输出为3。

计数法：

其实不通过奇数位置、偶数位置分别排序也可以求解，奇数位置、偶数位置排序后字符串相等《=》原字符串奇数位置各字母数量、偶数位置各字母数量相等，这两者是等价的。官方题解就是通过这个等价的转换求解的。对字符串数组A中的每个字符串用大小为52的int数组count存储该字符串的奇偶位置字母数量，前26个存储偶数下标字母数量、后26个存储奇数下标字母数量，最后数组转成字符串放入set集合中，因为一组特殊等价字符串中的字符串有字母数量转换后的字符串相等，所以最后set集合的大小就是A中特殊等价字符串组的数量。

这道题还挺好的，不是那么简单，还行😌

------------- THE END! THANKS! -------------