LeetCode Repeated DNA Sequences (JavaScript), Sliding window

링크 : https://leetcode.com/problems/repeated-dna-sequences/description/

문제 설명

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'.

---

문제 풀이

10글자의 문자열이 전체 문자열에 2번이상 나오는 문자열을 구하는 문제

접근 방식

(슬라이딩 윈도우 기법을 활용하여 풀이 -> 해당 문제에서는 간단한게 하기위해 substring 메서드를 이용)

1. 2개의 set 배열 선언
   • 한 번 등장할 경우 저장할 배열, 두 번 이상 등장할 경우 저장할 배열
2. 현재 index를 기준으로 10개의 문자열을 만듦(substring활용)
3. 해당 문자열이 한 번 등장 했다면 tmp에 저장
   • tmp에 이미 있다면 2번 이상 등장한 문자열이므로 repeat 배열에 저장
4. 최종적으로 repeat에 저장된 문자열이 위 문제의 조건을 만족하는 문자열임.
   • 리턴 값은 배열형태이기 때문에 ... 연산을 이용해 set -> array로 변환

/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function(s) {
    const tmp = new Set();
    const repeat = new Set();

    for (let i = 0; i <= s.length - 10; i++) {
        const target = s.substring(i, i + 10);

        if (tmp.has(target)) {
            repeat.add(target);
        } else {
            tmp.add(target);            
        }
    }

    return [...repeat];
};

---

결론

두 번 이상 등장 이라는 조건을 쉽게 파악하기 위해 set 배열을 두개 만들어 관리하는 방식이 이 문제의 핵심