LeetCode 187번 Repeated DNA Sequences JavaScript

문제

String.length가 10인 부분 문자열들 중에서 두 번 이상 나오는 문자열만 반환하는 문제이다.

문제 출처

187. Repeated DNA Sequences

나의 풀이

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

    for (let i = 0; i <= s.length - 10; i++) {
        const substr = s.slice(i, i + 10);
        
        if (seen.has(substr)) {
            repeated.add(substr);
        } else {
            seen.add(substr);
        }
    }

    return [...repeated];
};

풀이 설명

문자열을 고정된 크기 (String.length가 10)로 잘라가며 비교하는 문제이므로 슬라이딩 윈도우 방식으로 해결하면 된다.

슬라이딩 윈도우 (Sliding Window)
문자열이나 배열에서 고정된 크기의 윈도우를 한 칸씩 이동시키며 문제를 해결하는 알고리즘을 말한다.

이 문제에서는 문자열 s에서 길이가 10인 부분 문자열을 왼쪽에서 오른쪽으로 한 칸씩 이동해가며, 중복으로 등장하는 부분 문자열만 찾아야 한다.

중복 여부를 판단하기 위해 Set 객체를 활용해보자!

• seen: 한 번이라도 등장한 문자열을 저장한다.

• repeated: 두 번 이상 등장한 문자열만 저장한다.

문자열을 끝까지 탐색한 후, repeated에 저장된 값들을 배열로 변환하여 반환하면 된다.