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 1:**

**Tags:** Math, String

请编写一个程序，找到所有长度为10的且出现次数多于1的子串。

从前往后扫描，当子串出现第二次时，将其记录在答案中。

时间复杂度分析：总共约 nn 个长度是10的子串，所以总共有 10n10n 个字符。计算量与字符数量成正比，所以时间复杂度是 O(n)O(n)。

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]

[title]:https://leetcode.com/problems/repeated-dna-sequences/

[me]:https://github.com/kylesliu/awesome-golang-leetcode

package Solution

funcfindRepeatedDnaSequences(sstring) []string {

ans:=make([]string,0)

iflen(s)<10 {

}

cache:=make(map[string]int)

fori:=0;i<=len(s)-10;i++ {

curr:=s[i :i+10]

ifcache[curr]==1 {

ans=append(ans,curr)

}

cache[curr]+=1

}

}

package Solution

import (

)

funcTestSolution(t*testing.T) {

cases:= []struct {

expect []string

}{

{"TestCase","AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT", []string{"AAAAACCCCC","CCCCCAAAAA"}},

}

fori,c:=rangecases {

t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {

got:=findRepeatedDnaSequences(c.inputs)

if!reflect.DeepEqual(got,c.expect) {

t.Fatalf("expected: %v, but got: %v, with inputs: %v",

c.expect,got,c.inputs)

}

})

}

}

funcBenchmarkSolution(b*testing.B) {

}

funcExampleSolution() {

}