文章目录

原题

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

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
  • All A[i] have the same length.
  • All A[i] consist of only lowercase letters.

题解

明确题意

给定一个字符串向量vector 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的组成元素是否一致,即排序后的字符串是否一样。同理,判断奇数位的组成元素(字符)。

代码

[code lang=”cpp”]
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();
}
};
[/code]

复杂度

M 代表数组A的长度
N 代表A数组中最长的字符串的长度
时间复杂度:O(M*N*lgN)


原题:https://leetcode.com/problems/groups-of-special-equivalent-strings/

文章来源:胡小旭 => [LeetCode]893. Groups of Special-Equivalent Strings

Share:

2 comments

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.