[LeetCode] 187. Repeated DNA Sequences [Python] 해시셋

leetcode.com/problems/repeated-dna-sequences/

Repeated DNA Sequences - LeetCode

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.

 

이 문제는 반복되는 DNA의 시퀀스를 찾는 문제입니다. 해시를 이용하면 쉽게 풀 수 있는 문제입니다.

---

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        lut = set()
        ans = set()
        for i in range(10, len(s)+1):
            seq = s[i-10:i]
            if seq in lut: ans.add(seq)
            else: lut.add(seq)
        return ans

---

먼저 주어진 문자열을 10개의 문자단위로 끊어 스캔합니다. 스캔할 때마다 해시 셋에 저장을 합니다. 그리고 만약 스캔된 문자열이 lut에 저장이 되어있는 문자열이라면, ans에 해당 문자열을 추가합니다. 즉, lut는 내가 본 모든 시퀀스가 저장이 되어있고, ans는 두번 이상 본 시퀀스를 저장하는 것입니다. 그리고 간단하게 ans를 리턴해주면 문제는 해결됩니다. 해당 솔루션의 시간 복잡도는 O(n)이며, 공간 복잡도 역시 O(n)이 나옵니다.