Problem
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
- AllĀ
A[i]
Ā have the same length.
- AllĀ
A[i]
Ā consist of only lowercase letters.
Ā
Solution: Signature
All Special-Equivalent Strings should have the same signature if we sort all the odd-index characters and all the even-index characters.
E.g.Ā [“abcd”,”cdab”,”adcb”,”cbad”] are all in the same graph.
“abcd”: odd “ac”, even: “bd”
“cdab”: odd “ac”, even: “bd”
“adcb”: odd “ac”, even: “bd”
“cbad”: odd “ac”, even: “bd”
We can concatenate the odd and even strings to create a hashable signature.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 8 ms class Solution { public: int numSpecialEquivGroups(vector<string>& A) { unordered_set<string> s; for (const string& a : A) { string odd; string even; for (int i = 0; i < a.size(); ++i) { if (i % 2) odd += a[i]; else even += a[i]; } sort(begin(odd), end(odd)); sort(begin(even), end(even)); s.insert(odd + even); } return s.size(); } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 16 ms class Solution { public int numSpecialEquivGroups(String[] A) { Set<String> groups = new HashSet<>(); for (String a: A) { char[] odd = new char[(a.length() + 1) / 2]; char[] even = new char[(a.length() + 1) / 2]; for (int i = 0; i < a.length(); ++i) { if (i % 2 == 0) even[i / 2] = a.charAt(i); else odd[i / 2] = a.charAt(i); } Arrays.sort(odd); Arrays.sort(even); String s = new String(odd) + new String(even); groups.add(s); } return groups.size(); } } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
""" Author: Huahua Running time: 56 ms """ class Solution: def numSpecialEquivGroups(self, A): s = set() for a in A: odd = "" even = "" for i, c in enumerate(a): if i % 2 == 0: odd += c else: even += c s.add(''.join(sorted(odd) + sorted(even))) return len(s) |
Python (1-linear)
|
""" Author: Huahua Running time: 56 ms """ class Solution: def numSpecialEquivGroups(self, A): return len(set([''.join(sorted(a[0::2]) + sorted(a[1::2])) for a in A])) |