LeetCode.893-特殊相等字符串组(Groups of Special-Equivalent Strings)

这是悦乐书的第ong>344ong>次更新,第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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgwzpy.html