LeetCode - 187. Repeated DNA Sequences (JavaScript)

Medium, 문자열, 집합

RunTime : 68 ms / Memory : 60.45 MB

문제

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.

풀이

• 시간초과 난 풀이
  • Set()이 아닌 Object 사용
  • includes()에서 시간소요 발생

var findRepeatedDnaSequences = function(s) {
    var tmp = {};
    var res = [];
    for(let i = 0; i < s.length - 9; i++){
        let now = s.slice(i, i + 10);
        if(Object.keys(tmp).includes(now)){
            tmp[now] += 1;
        } else {
            tmp[now] = 1;
        }
    }
    for(let key in tmp){
        if(tmp[key] >= 2){
            res.push(key);
        }
    }
    return res;
};

• Object를 Set을 통해 변환해 값이 유무 확인에 시간 소요를 줄인 풀이

var findRepeatedDnaSequences = function(s) {
    var tmp = new Set();
    var res = new Set();
    if(s.length < 10){
        return [];
    }

    for(let i = 0; i < s.length - 9; i++){
        let now = s.slice(i, i + 10);
        if(tmp.has(now)){
            res.add(now);
        } else {
            tmp.add(now);
        }
    }
    
    return [...res];
};