[Swift]LeetCode893. 特殊等价字符串组 | Groups of Special-Equivalent Strings
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10605452.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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: 3 Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]
Example 2:
Input: 4 Explanation: 4 groups
Example 3:
Input: 3 Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]
Example 4:
Input: 1 Explanation: 1 group
Note:
1 <= A.length <= 10001 <= A[i].length <= 20- All
A[i]have the same length. - All
A[i]consist of only lowercase letters.
你将得到一个字符串数组 A。
如果经过任意次数的移动，S == T，那么两个字符串 S 和 T 是特殊等价的。
一次移动包括选择两个索引 i 和 j，且 i％2 == j％2，并且交换 S[j] 和 S [i]。
现在规定，A 中的特殊等价字符串组是 A 的非空子集 S，这样不在 S 中的任何字符串与 S 中的任何字符串都不是特殊等价的。
返回 A 中特殊等价字符串组的数量。
示例 1：
输入：["a","b","c","a","c","c"] 输出：3 解释：3 组 ["a","a"]，["b"]，["c","c","c"]
示例 2：
输入：["aa","bb","ab","ba"] 输出：4 解释：4 组 ["aa"]，["bb"]，["ab"]，["ba"]
示例 3：
输入：["abc","acb","bac","bca","cab","cba"] 输出：3 解释：3 组 ["abc","cba"]，["acb","bca"]，["bac","cab"]
示例 4：
输入：["abcd","cdab","adcb","cbad"] 输出：1 解释：1 组 ["abcd","cdab","adcb","cbad"]
提示：
1 <= A.length <= 10001 <= A[i].length <= 20- 所有
A[i]都具有相同的长度。 - 所有
A[i]都只由小写字母组成。
40ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 var specialEquivalentStringCountSet = Set<[Int]>()
4 for str in A {
5 specialEquivalentStringCountSet.insert(getStringPartion(source: str))
6 }
7 return specialEquivalentStringCountSet.count
8 }
9 private func getStringPartion(source: String) -> [Int] {
10 var result = Array<Int>(repeating: 0, count: 52)
11 var index = 0
12 for char in source.utf8 {
13 let tempIndex = 26 * (index % 2 == 0 ? 0 : 1) + Int(char) - 97
14 result[tempIndex] = result[tempIndex] + 1
15 index += 1
16 }
17 return result
18 }
19 }52ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 var result = Set<[Character]>()
4 for string in A {
5 var str1: String = ""
6 var str2: String = ""
7 var even = true
8 for c in string {
9 if even {
10 str1.append(c)
11 } else {
12 str2.append(c)
13 }
14 even = !even
15 }
16 result.insert(str1.sorted() + str2.sorted())
17 }
18 return result.count
19 }
20 }64ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 var set = Set<String>()
4 for word in A{
5 var evenString = ""
6 var oddString = ""
7 for (index, char) in word.enumerated(){
8 if index % 2 == 0{
9 evenString.append(char)
10 }
11 else{
12 oddString.append(char)
13 }
14 }
15 set.insert(String(evenString.sorted()) + String(oddString.sorted()))
16 }
17 return set.count
18 }
19 }68ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 var array = [String]()
4 for s in A {
5 let temp = Array(s)
6 var preStr = [Character]()
7 var sufStr = [Character]()
8 for i in 0..<temp.count{
9 if i%2==0 {
10 preStr.append(temp[i])
11 }else {
12 sufStr.append(temp[i])
13 }
14 }
15 preStr = preStr.sorted()
16 sufStr = sufStr.sorted()
17 array.append(String(preStr+sufStr))
18 }
19 return Set(array).count
20 }
21 }84ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 var dict = [String: Int]()
4 for item in A {
5 let chars = Array(item)
6 var odd = [Character]()
7 var even = [Character]()
8 for i in 0..<chars.count {
9 if i % 2 == 0 {
10 even.append(chars[i])
11 } else {
12 odd.append(chars[i])
13 }
14 }
15 odd.sort()
16 even.sort()
17 let current = odd.reduce("") { $0 + String($1) } + even.reduce("") { $0 + String($1) }
18 dict[current] = dict[current] ?? 0
19 dict[current]! += 1
20 }
21 return dict.count
22 }
23 }88ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 return Set(A.map { tokenize($0) }).count
4 }
5
6 private func tokenize(_ str: String) -> Token {
7 var even = [Character: Int]()
8 var odd = [Character: Int]()
9
10 for (i, c) in Array(str).enumerated() {
11 if i % 2 == 0 {
12 even[c] = (even[c] ?? 0) + 1
13 } else {
14 odd[c] = (odd[c] ?? 0) + 1
15 }
16 }
17
18 return Token(even: even, odd: odd)
19 }
20
21 private struct Token: Hashable {
22 let even: [Character: Int]
23 let odd: [Character: Int]
24 }
25 }92ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 var dict = [String: Int]()
4 for item in A {
5 let chars = Array(item)
6 var count = [Int](repeating: 0, count: 52)
7 for i in 0..<chars.count {
8 count[Int(UnicodeScalar(String(chars[i]))!.value) - Int(UnicodeScalar("a")!.value) + 26 * (i % 2)] += 1
9 }
10
11 let current = count.reduce("") { $0 + String($1) }
12 dict[current] = dict[current] ?? 0
13 }
14 return dict.count
15 }
16 }Runtime: 92 ms
Memory Usage: 20.2 MB
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 var set:Set<String> = Set<String>()
4 for s in A
5 {
6 var odd:[Int] = [Int](repeating:0,count:26)
7 var even:[Int] = [Int](repeating:0,count:26)
8 let arrS:[Character] = Array(s)
9 for i in 0..<s.count
10 {
11 if i % 2 == 1
12 {
13 odd[arrS[i].ascii - 97] += 1
14 }
15 else
16 {
17 even[arrS[i].ascii - 97] += 1
18 }
19 }
20 var oddChar:[Character] = odd.map{$0.ASCII}
21 var evenChar:[Character] = even.map{$0.ASCII}
22 var sig:String = String(oddChar) + String(evenChar)
23 set.insert(sig)
24 }
25 return set.count
26 }
27 }
28
29 //Character扩展
30 extension Character
31 {
32 //Character转ASCII整数值(定义小写为整数值)
33 var ascii: Int {
34 get {
35 return Int(self.unicodeScalars.first?.value ?? 0)
36 }
37 }
38 }
39
40 //Int扩展
41 extension Int
42 {
43 //Int转Character,ASCII值(定义大写为字符值)
44 var ASCII:Character
45 {
46 get {return Character(UnicodeScalar(self)!)}
47 }
48 }100ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 let s = Set(A.map { (s: String) -> String in
4 let cs = Array(s).enumerated()
5 let s1 = String(cs.filter {$0.0 % 2 == 0}.map {$0.1}.sorted())
6 let s2 = String(cs.filter {$0.0 % 2 == 1}.map {$0.1}.sorted())
7 return s1 + s2
8 })
9 return s.count
10 }
11 }132ms
1 class Solution {
2 func numSpecialEquivGroups(_ A: [String]) -> Int {
3 var c = Set<String>()
4 let aVal = "a".unicodeScalars.first!.value
5 for word in A {
6 var d = [Int](repeating:0, count:54)
7 for (index, char) in word.enumerated() {
8 let i = 26 * (index%2) + Int(char.unicodeScalars.first!.value - aVal)
9 d[i] = d[i] + 1
10 }
11 var output = String()
12 for i in 0 ..< d.count {
13 output.append("\(d[i]) ")
14 }
15 c.insert(output)
16 }
17 return c.count
18 }
19 }