本文主要是介绍重复的DNA序列(LeetCdoe),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
DNA序列 由一系列核苷酸组成,缩写为
'A'
,'C'
,'G'
和'T'
.。
- 例如,
"ACGAATTCCG"
是一个 DNA序列 。在研究 DNA 时,识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串
s
,返回所有在 DNA 分子中出现不止一次的 长度为10
的序列(子字符串)。你可以按 任意顺序 返回答案。
解题
"""
时间复杂度: O(n),其中 n 是字符串的长度。因为我们只需要遍历一次字符串。
空间复杂度: O(n),因为需要存储所有长度为 10 的子串。
"""def findRepeatedDnaSequences(s):# 用于存储已经见过的子串seen = set()# 用于存储重复的子串repeated = set()# 遍历字符串,找出每个长度为10的子串for i in range(len(s) - 9):sequence = s[i:i + 10]# 如果子串已经在seen中,说明重复了,加入repeatedif sequence in seen:repeated.add(sequence)else:seen.add(sequence)# 返回重复的子串return list(repeated)# 测试
s = "ACGAATTCCGACGAATTCCG"
print(findRepeatedDnaSequences(s)) # ['ACGAATTCCG']
这篇关于重复的DNA序列(LeetCdoe)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!