内容简介：You are given an arrayTwo stringsA
原题
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:
Input: ["a","b","c","a","c","c"] Output: 3 Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]
Example 2:
Input: ["aa","bb","ab","ba"] Output: 4 Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]
Example 3:
Input: ["abc","acb","bac","bca","cab","cba"] Output: 3 Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]
Example 4:
Input: ["abcd","cdab","adcb","cbad"] Output: 1 Explanation: 1 group ["abcd","cdab","adcb","cbad"]
Note:
1 <= A.length <= 1000 1 <= A[i].length <= 20 A[i] A[i]
题解
明确题意
A。
然后，定义一个Special-Equivalent概念，如果有两个字符串S和T，将S串中的奇数位置相互移动若干次或不移动，偶数位置相互移动若干次或不移动之后，可以使两个字符串S和T相等，那么称为S和T是Special Equivalent。
思路
奇数位和偶数位是两个分类，但是是一个纬度，如果解决了奇数位，那么就解决了偶数位。
所以，先考虑偶数位。SE（even for string S）和TE（odd for string T）。判断SE和TE能否通过调整各自内部字符的位置达到一致的问题，其实就是判断SE和TE的组成元素是否一致，即 排序 后的字符串是否一样。同理，判断奇数位的组成元素（字符）。
代码
class Solution {
public:
int numSpecialEquivGroups(vector<string>& A) {
map<string, int> a;
string es, os;
for (auto str : A) {
es = os = "";
for (int i = 0; i < str.length(); ++i) {
if (i % 2 == 0) es += str[i];
if (i % 2 == 1) os += str[i];
}
sort(es.begin(), es.end());
sort(os.begin(), os.end());
a[es + os] += 1;
}
return a.size();
}
};
复杂度
M 代表数组A的长度
N 代表A数组中最长的字符串的长度
时间复杂度：O(M*N*lgN)
原题： https://leetcode.com/problems/groups-of-special-equivalent-strings/
文章来源： 胡小旭 => [LeetCode]893. Groups of Special-Equivalent Strings
以上所述就是小编给大家介绍的《[LeetCode]893. Groups of Special-Equivalent Strings》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- [LeetCode]893. Groups of Special-Equivalent Strings
- Leetcode PHP题解--D46 893. Groups of Special-Equivalent Strings
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
