描述
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:
1 | Input: ["a","b","c","a","c","c"] |
Example 2:
1 | Input: ["aa","bb","ab","ba"] |
Example 3:
1 | Input: ["abc","acb","bac","bca","cab","cba"] |
Example 4:
1 | Input: ["abcd","cdab","adcb","cbad"] |
Note:
1 <= A.length <= 1000
1 <= A[i].length <= 20
- All
A[i]
have the same length. - All
A[i]
consist of only lowercase letters.
分析
题目大意是给定一个包含字符串的集合,对于一些字符串,如果对于奇数位置的字符和偶数位置的字符任意调换顺序,得到的结果是一样的,那么这些字符串属于同一个组,要求根据输入的集合得出这个集合有几个组。
可以分别将字符串里的奇数位置的字符和偶数位置的字符进行排序,排序的结果放入一个哈希集合,最后这个哈希集合的大小就是组的数量。这个『排序』的过程可以用通过增加空间复杂度的方式实现,也可以用排序实现
解决方案1(Java)
1 | class Solution { |