LeetCode 187 - Repeated DNA Sequences (Medium)

문제

LeetCode - 187번

풀이 과정

주어진 문자열에서 10자 이상의 부분 문자열 중 2번 이상 반복되는 모든 부분 문자열의 종류를 찾는 문제입니다.

해시 테이블 를 사용하면 O(N) 에 모든 경우를 탐색할 수 있습니다.
이외에도 두 개의 Set 을 사용하면 동일한 로직을 수행할 수도 있습니다. (구현은 이게 더 깔끔한 것 같습니다 😄)

코드

/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function (s) {
  if (s.length < 10) return [];

  const cache = new Map();

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

    if (cache.has(substring)) {
      const quantity = cache.get(substring);
      cache.set(substring, quantity + 1);
    } else {
      cache.set(substring, 0);
    }
  }

  const answer = [...cache.entries()].reduce((acc, [key, value]) => {
    if (value >= 1) acc.push(key);
    return acc;
  }, []);

  return answer;
};