DNA序列 由一系列核苷酸組成，縮寫為 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG"?是一個 DNA序列 。
在研究 DNA 時，識別 DNA 中的重復(fù)序列非常有用。

給定一個表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出現(xiàn)不止一次的 長度為 10 的序列(子字符串)。你可以按 任意順序 返回答案。

示例 1：

輸入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
輸出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

輸入：s = "AAAAAAAAAAAAA"
輸出：["AAAAAAAAAA"]

示例代碼1： 【哈希表】

from collections import defaultdictclass Solution(object):def findRepeatedDnaSequences(self, s):l = 10dic = defaultdict(int)ans = []for i in range(len(s) - l + 1):res = s[i:i + l]dic[res] += 1if dic[res] == 2:ans.append(res)return anss = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" obj = Solution() ret = obj.findRepeatedDnaSequences(s) print(ret)

思路分析：

• 使用哈希表統(tǒng)計 s?所有長度為 10的子串的出現(xiàn)次數(shù)，返回所有出現(xiàn)次數(shù)超過 10的子串。
• 代碼實現(xiàn)時，一邊遍歷子串一邊記錄答案，為了不重復(fù)記錄答案，只統(tǒng)計當(dāng)前出現(xiàn)次數(shù)為 2?的子串。

復(fù)雜度分析：

• 時間復(fù)雜度：O(NL)，其中 N?是字符串s 的長度，L=10即目標(biāo)子串的長度。
• 空間復(fù)雜度：O(NL)。

示例代碼2：? 【滑動窗口】

class Solution(object):def findRepeatedDnaSequences(self, s):l = 10if len(s) < l:return []ans, window = set(), set()for i in range(len(s) - l + 1):tmp = s[i:i + l]if tmp not in window:window.add(tmp)else:ans.add(tmp)return list(ans)s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" s = "AAAAAAAAAAA" obj = Solution() ret = obj.findRepeatedDnaSequences(s) print(ret)

總結(jié)

以上是生活随笔為你收集整理的重复的DNA序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。