这是悦乐书的第344次更新，第368篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第209题（顺位题号是893）。
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.
给定一个字符串数组A。
如果在任意数量的移动之后，两个字符串S和T是特殊相等的，S == T。
移动是指选择两个索引i和j，其中i％2 == j％2，并且用S[j]交换S[i]。
现在，S是一个特殊相等字符串组，是A的非空子集，使得不存在于S中（但存在于A中）的任意字符串与S中的任何字符串不是特殊相等的。
返回A中特殊相等字符串组的数量。例如：
输入：[“a”，“b”，“c”，“a”，“c”，“c”]
输出：3
说明：3组[“a”，“a”]，[“b”]，[“c”，“c”，“c”]
输入：[“aa”，“bb”，“ab”，“ba”]
输出：4
说明：4组[“aa”]，[“bb”]，[“ab”]，[“ba”]
输入：[“abc”，“acb”，“bac”，“bca”，“cab”，“cba”]
输出：3
说明：3组[“abc”，“cba”]，[“acb”，“bca”]，[“bac”，“cab”]
输入：[“abcd”，“cdab”，“adcb”，“cbad”]
输出：1
说明：1组[“abcd”，“cdab”，“adcb”，“cbad”]
注意：
-
1 <= A.length <= 1000
-
1 <= A [i] .length <= 20
-
所有A [i]具有相同的长度。
-
所有A [i]仅包含小写字母。
02 理解题意
起初看这道题的题目描述看的是一脸懵逼，不知道它要表达的是什么意思，更不谈如何解题了。
只能硬着头皮看了，已经记不得看了多少遍了，结合它给的四个例子，终于是明白了它想要表达的意思，上面的中文描述是我在谷歌翻译的基础上做了润色的，方便理解，不信邪的人可以直接看英文描述，可以看到你怀疑人生！
题目说两个字符串S和J可以任意交换字符，但是有个前提i％2 == j％2，也就是说S的奇数位只能和奇数位换，S的偶数位只能和偶数位换，J的交换同理，换完之后要是S和J相等，就是特殊相等。
现在又有个特殊相等字符串组的概念，就是由那些特殊相等字符串组成的小帮派，每个小帮派里面的字符串，都符合上面的转换规则.问A中有多少个这样的小帮派？
结合例四来讲，很快你就会明白题目究竟是个神马意思了。
第四个例子中，A = [“abcd”，“cdab”，“adcb”，“cbad”]，最后输出是特殊相等字符串组的数量为1，我们来一起看看这个1是怎么算出来的。
先对"abcd"转换一把，'a'、'c'可以互换，'b'、'd'可以互换，题目既然说了是任意互换，也就是说不论先后顺序，那我们就统一按照从小到大的顺序来，转换完之后就变成"ac" + "bd"="acbd"。
按照这样的逻辑，对"cdab"、"adcb"、"cbad"进行转换后，都变成了"acbd"，所以最后只存在1个帮派了，就是"acbd"。
03 第一种解法
在处理每个单独的字符串时，利用一个26位长度的int数组，记录每个字符出现的次数，对奇数位、偶数维分开处理，然后将两数组转成一个新的字符串拼接在一起，存入HashSet中，最后特殊相等字符串组的数量就是HashSet的size了。
public int numSpecialEquivGroups(String[] A) {
Set<String> set = new HashSet<String>();
for (String str : A) {
int[] odd = new int[26];
int[] even = new int[26];
for (int i=0; i<str.length(); i++) {
if (i%2 == 0) {
even[str.charAt(i)-'a']++;
} else {
odd[str.charAt(i)-'a']++;
}
}
String newStr = Arrays.toString(odd)+Arrays.toString(even);
set.add(newStr);
}
return set.size();
}
04 第二种解法
我们可以对上面的解法再优化下，只用一个int数组，但是长度变为52，前半部分存偶数位，后半部分村奇数位，最后再转成字符串，存入HashSet中，最后特殊相等字符串组的数量就是HashSet的size了。
public int numSpecialEquivGroups2(String[] A) {
Set<String> set = new HashSet<String>();
for (String str : A) {
int[] count = new int[52];
for (int i=0; i<str.length(); i++) {
count[str.charAt(i)-'a'+26*(i%2)]++;
}
set.add(Arrays.toString(count));
}
return set.size();
}
05 小结
算法专题目前已连续日更超过六个月，算法题文章212+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论