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 <= 10001 <= 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)
|
1 2 3 4 5 6 7 |
""" 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])) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment