[99클럽 코테스터디 TIL 15일차] LeetCode 187. Repeated DNA Sequences 해설 및 풀이 (Java)

 

LeetCode 187. Repeated DNA Sequences

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

---

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

For example, "ACGAATTCCG" is a DNA sequence.
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.

 

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]
Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
 

Constraints:

1 <= s.length <= 105
s[i] is either 'A', 'C', 'G', or 'T'.

 

한글 해석

DNA 서열은'A' , 'C', 'G', 로 약칭되는 일련의 뉴클레오티드로 구성됩니다 'T'.

예를 들어, DNA 서열"ACGAATTCCG" 은 .
DNA를 연구할 때 , DNA 내에서 반복되는 서열을 식별하는 것이 유용합니다.

DNA 서열을s 나타내는 문자열이 주어지면 , DNA 분자에서 두 번 이상 나타나는 모든 -글자 길이의 서열(부분 문자열)을 반환합니다. 답은 어떤 순서 로든 반환할 수 있습니다 .10

 

예시 1:

입력: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
 출력: ["AAAAACCCCC","CCCCCAAAAA"]
예 2:

입력: s = "AAAAAAAAAAAA"
 출력: ["AAAAAAAAAA"]
 

제약 조건:

1 <= s.length <= 105
s[i]'A', 'C', 'G', 또는 입니다 'T'.

 

---

 

 

문제 유형

 

Hash Table
String
Bit Manipulation
Sliding Window
Rolling Hash
Hash Function

 

풀이 방법 도출

 

1. 문자열을 인덱스 0부터 끝까지 반복하면서 10글자짜리 부분 문자열을 잘라냅니다.
2. 처음 본 문자열은 set에 저장하고 이미 본 문자열이면 result에 저장합니다.
3. 중복된 부분 문자열만 결과에 저장합니다.

 

시간 복잡도

• O(n)

---

핵심 코드 삽입 및 설명

 

import java.util.*;

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        // 이미 나온 10글자 부분 문자열 저장
        Set<String> set = new HashSet<>();
        // 중복으로 두 번 이상 나온 10글자 문자열 저장
        Set<String> result = new HashSet<>();
        
        // 전체 문자열을 순회하면서 길이를 10짜리 부분 문자열 추출
        for (int i = 0; i <= s.length() - 10; i++) {
            // 길이 10의 부분 문자열 추출
            String substring = s.substring(i, i + 10);
            
            // set에 추가 실패했다는 것은 이미 한 번 등장함
            // 따라서 result에 추가
            if (!set.add(substring)) {
                result.add(substring);
            }
        }

        // Set을 List로 변환하여 결과 반환
        return new ArrayList<>(result);
    }
}