[Swift]LeetCode187.重复的DNA序列|RepeatedDNASequences

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

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

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

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

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

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

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出: ["AAAAACCCCC", "CCCCCAAAAA"]

84ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3         guard s.count >= 10 else {
 4             return []
 5         }
 6         var characters = Array(s)
 7         var result = Set<String>()
 8         var dic = [Int : Int]()
 9         var map: [Character : Int] = ["A" : 0, "C" : 1, "G" : 2, "T" : 3]
10         var cur = 0, i = 0
11         while i < 9 {
12             let num = map[characters[i]]!
13             cur = cur << 2 | (num & 3)
14             i += 1
15         }
16         let count = s.count
17         while i < count {
18             let num = map[characters[i]]!
19             cur = ((cur & 0x3ffff) << 2) | (num & 3)
20             i += 1
21             if let _ = dic[cur] {
22                 let startIndex = s.index(s.startIndex, offsetBy: i - 10)
23                 let endIndex = s.index(s.startIndex, offsetBy: i)
24                 result.insert(String(s[startIndex..<endIndex]))
25             } else {
26                 dic[cur] = 1
27             }
28         }
29         
30         return Array(result)
31         
32     }
33     
34 }

92ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3 
 4         guard s.count >= 10 else { return [] }
 5       
 6         var m = [Int: Int]()
 7         var res = [String]()
 8          var charDict: [Character: Int] = ["A": 0, "C" : 1, "G" : 2, "T" : 3]
 9         var base = 256*256*4 //pow(4, 9) 
10         var chars = Array(s)
11         var num = 0
12         for i in 0..<9 {
13             num *= 4
14             num += (charDict[chars[i]] ?? 0 )
15         }
16         for i in 9..<chars.count {
17             num %= base
18             num *= 4
19             num += (charDict[chars[i]] ?? 0 )
20         
21             m[num, default:0] += 1
22             if m[num, default:0] == 2 {
23                 res.append(String(chars[i-9...i]))
24             }
25         }
26         return res
27     }
28 }
29 
30 extension String {
31     func substring(_ i: Int, _ len: Int) -> String {
32         var startInd = index(startIndex, offsetBy: i)
33         var endInd = index(startIndex, offsetBy: i+len)
34         return String(self[startInd..<endInd])
35     }
36 }

316ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3         guard s.count >= 10 else { return [] }
 4         let chars = Array(s)
 5 
 6         var (seen, repeated) = (Set<String>(), Set<String>())
 7 
 8         for i in 0 ..< (chars.count - 9) {
 9             let cur = String(chars[i ... (i + 9)])
10             if !seen.insert(cur).inserted {
11                 repeated.insert(cur)
12             }
13         }
14 
15         return Array(repeated)
16     }
17 }

412ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3         let array = Array(s)
 4         var map: Dictionary<String, Int> = [:]
 5         var result: [String] = []
 6         
 7         if (array.count <= 10) {
 8             return []
 9         }
10         
11         for i in 0 ..< array.count - 9 {
12             let str = String(array[i ..< i + 10])
13             
14             if let count = map[str] {
15                 if (count == 1) {
16                     result.append(str)
17                 }
18                 map[str] = count + 1
19             } else {
20                 map[str] = 1
21             }
22         }
23         
24         return result
25     }
26 }

432ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3         let len = s.count
 4         if len <= 10 {
 5             return []
 6         }
 7         var sArr = s.map { $0 }
 8         var set = Set<String>()
 9         var res = [String]()
10         var temp: String
11         for i in 0 ... len - 10 {
12             temp = String(sArr[i ..< i + 10])
13             if set.contains(temp) {
14                 if !res.contains(temp) {
15                     res.append(temp)
16                 }
17             } else {
18                 set.insert(temp)
19             }
20         }
21         
22         return res
23     }
24 }