[Swift]LeetCode187. 重复的DNA序列 | Repeated DNA Sequences_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

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"]

超出时间限制

 1 class Solution { 2     func findRepeatedDnaSequences(_ s: String) -> [String] { 3         if s.count < 9 {return []} 4         var res:Set<String> = Set<String>() 5         var st:Set<String> = Set<String>() 6         for i in 0..<(s.count - 9) 7         { 8             var t:String = s.subString(i,10) 9             if st.contains(t)10             {11                 res.insert(t)12             }13             else14             {15                 st.insert(t)16             }17         }18         //Set转数组[String]19         return Array(res)20     }21 }22 23 extension String {24     // 截取字符串：指定索引和字符数25     // - begin: 开始截取处索引26     // - count: 截取的字符数量27     func subString(_ begin:Int,_ count:Int) -> String {28         let start = self.index(self.startIndex,offsetBy: max(0,begin))29         let end = self.index(self.startIndex,offsetBy:  min(self.count,begin + count))30         return String(self[start..<end]) 31     }32     33 }

超出时间限制

 1 class Solution { 2     func findRepeatedDnaSequences(_ s: String) -> [String] { 3         if s.count < 9 {return []} 4         var res:Set<String> = Set<String>() 5         var st:Set<String> = Set<String>() 6         var cur:Int = 0 7         for i in 0..<9 8         { 9             cur = cur << 3 | (s[i].ascii & 7)10         }11         12         for i in 9..<s.count13         {14             cur = ((cur & 0x7ffffff) << 3) | (s[i].ascii & 7)15             var t:String = s.subString(i - 9,10)16             if st.contains(t)17             {18                 res.insert(t)19             }20             else21             {22                 st.insert(t)23             }24         }25         26         //Set转数组[String]27         return Array(res)28     }29 }30 31 extension String {32     //subscript函数可以检索数组中的值33     //直接按照索引方式截取指定索引的字符34     subscript (_ i: Int) -> Character {35         //读取字符36         get {return self[index(startIndex,offsetBy: i)]}37     }38     39     // 截取字符串：指定索引和字符数40     // - begin: 开始截取处索引41     // - count: 截取的字符数量42     func subString(_ begin:Int,_ count:Int) -> String {43         let start = self.index(self.startIndex,begin))44         let end = self.index(self.startIndex,begin + count))45         return String(self[start..<end]) 46     }47     48 }49 50 //Character扩展方法  51 extension Character  52 {  53   //属性：ASCII整数值(定义小写为整数值)54    var ascii: Int {55         get {56             let s = String(self).unicodeScalars57             return Int(s[s.startIndex].value)58         }59     }60 }