0187. Repeated D N a Sequences

# 187. Repeated DNA Sequences#

## 题目 #

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

## 解题思路 #

• 这一题不用位运算比较好做，维护一个长度为 10 的字符串，在 map 中出现次数 > 1 就输出。
• 用位运算想做这一题，需要动态的维护长度为 10 的 hashkey，先计算开头长度为 9 的 hash，在往后面扫描的过程中，如果长度超过了 10 ，就移除 hash 开头的一个字符，加入后面一个字符。具体做法是先将 ATCG 变成 00，01，10，11 的编码，那么长度为 10 ，hashkey 就需要维护在 20 位。mask = 0xFFFFF 就是 20 位的。维护了 hashkey 以后，根据这个 hashkey 进行去重和统计频次。

## 代码 #

``````
package leetcode

// 解法一
func findRepeatedDnaSequences(s string) []string {
if len(s) < 10 {
return nil
}
charMap, mp, result := map[uint8]uint32{'A': 0, 'C': 1, 'G': 2, 'T': 3}, make(map[uint32]int, 0), []string{}
var cur uint32
for i := 0; i < 9; i++ { // 前9位，忽略
cur = cur<<2 | charMap[s[i]]
}
for i := 9; i < len(s); i++ {
cur = ((cur << 2) & 0xFFFFF) | charMap[s[i]]
if mp[cur] == 0 {
mp[cur] = 1
} else if mp[cur] == 1 { // >2，重复
mp[cur] = 2
result = append(result, s[i-9:i+1])
}
}
return result
}

// 解法二
func findRepeatedDnaSequences1(s string) []string {
if len(s) < 10 {
return []string{}
}
ans, cache := make([]string, 0), make(map[string]int)
for i := 0; i <= len(s)-10; i++ {
curr := string(s[i : i+10])
if cache[curr] == 1 {
ans = append(ans, curr)
}
cache[curr]++
}
return ans
}

``````

Apr 8, 2023