diff options
author | Jack Sangdahl <[email protected]> | 2024-08-30 18:16:42 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-30 18:16:42 -0600 |
commit | 48154c27a07e1216ae206613e58393aa853e6f38 (patch) | |
tree | fe90d2092eac3996ae07c7008690f05e11164c82 /repeated_dna_sequences.py | |
parent | accfdfe3a52d62bee9b2c24dece6f2b613ceeb7c (diff) | |
download | leetcode-48154c27a07e1216ae206613e58393aa853e6f38.tar.gz leetcode-48154c27a07e1216ae206613e58393aa853e6f38.zip |
187. repeated dna sequences
Diffstat (limited to 'repeated_dna_sequences.py')
-rw-r--r-- | repeated_dna_sequences.py | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/repeated_dna_sequences.py b/repeated_dna_sequences.py new file mode 100644 index 0000000..175fd9a --- /dev/null +++ b/repeated_dna_sequences.py @@ -0,0 +1,28 @@ +# 187. Repeated DNA Sequences +from collections import defaultdict + +""" +the dna sequence is composed of a series of nucleotides abbreviated as A, C, +G, and T. when studying dna it is useful to identify repeated sequences +within the dna. given a string 's' that represents a dna sequence, return all +the 10 letter long sequences (substrings) that occur more than once in a dna +molecule. you may return the answer in any order +""" + + +class Solution(object): + def findRepeatedDnaSequences(self, s): + """ + :type s: str + :rtype: List[str] + """ + seq = defaultdict(int) + for i in range(len(s)): + seq[s[i : i + 10]] += 1 + return [key for key, val in seq.iteritems() if val > 1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.findRepeatedDnaSequences(s="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT")) + print(obj.findRepeatedDnaSequences(s="AAAAAAAAAAAAA")) |