[Swift]LeetCode893.特殊等价字符串组|GroupsofSpecial-EquivalentStrings

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10605452.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 <= 1000
1 <= 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 <= 1000
1 <= 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 }