187. Repeated DNA Sequences
DNA 序列由一系列縮寫為 'A'、'C'、'G' 和 'T' 的核苷酸組成。
例如，"ACGAATTCCG" 是一個 DNA 序列。 在研究 DNA 時，識別 DNA 中的重複序列是很有用的。
給定一個表示 DNA 序列的字符串 s，返回所有出現多次且長度為 10 的序列（子串）。你可以按任意順序返回答案。
範例：
輸入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
輸出：["AAAAACCCCC","CCCCCAAAAA"]
Python
from typing import List
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
# If the string is shorter than 10 characters, there can't be any 10-letter-long sequences
if len(s) < 10:
return []
# Dictionary to store the count of each 10-letter-long sequence
sequence_count = {}
result = []
# Iterate through the string and record each 10-letter-long sequence
for i in range(len(s) - 9): # len(s) - 9 to avoid out-of-bound errors
sequence = s[i:i + 10]
if sequence in sequence_count:
sequence_count[sequence] += 1
else:
sequence_count[sequence] = 1
# Find all sequences that appear more than once
for sequence, count in sequence_count.items():
if count > 1:
result.append(sequence)
return result
27.92MB, 53ms
C++
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
// If the string is shorter than 10 characters, there can't be any 10-letter-long sequences
if (s.size() < 10) {
return {};
}
// Map to store the count of each 10-letter-long sequence
unordered_map<string, int> sequence_count;
vector<string> result;
// Iterate through the string and record each 10-letter-long sequence
for (size_t i = 0; i <= s.size() - 10; ++i) {
string sequence = s.substr(i, 10);
sequence_count[sequence]++;
}
// Find all sequences that appear more than once
for (const auto& pair : sequence_count) {
if (pair.second > 1) {
result.push_back(pair.first);
}
}
return result;
}
};
27.25MB, 54ms
Javascript
/**
* @param {string} s
* @return {string[]}
*/
var findRepeatedDnaSequences = function(s) {
// If the string is shorter than 10 characters, there can't be any 10-letter-long sequences
if (s.length < 10) {
return [];
}
// Map to store the count of each 10-letter-long sequence
const sequenceCount = new Map();
const result = [];
// Iterate through the string and record each 10-letter-long sequence
for (let i = 0; i <= s.length - 10; i++) {
const sequence = s.substring(i, i + 10);
sequenceCount.set(sequence, (sequenceCount.get(sequence) || 0) + 1);
}
// Find all sequences that appear more than once
for (const [sequence, count] of sequenceCount.entries()) {
if (count > 1) {
result.push(sequence);
}
}
return result;
};
65.97MB, 73ms
