Leetcode 187) Repeated DNA Sequences

16 May 2021 in Algorithms

• 나는 hashmap에 넣어서 숫자가 key의 value가 2 이상일 경우 그걸 result list에 넣어줬다.

  if(DNA.containsKey(dna)){
      int val = DNA.get(dna); 
      DNA.put(dna,++val);
  }
  

  • 이 코드 대신, 바로 result 어레이에 추가하면 된다.

import java.util.*;
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        //범위 정할 때 구체적으로 예시들면서 정하면 더 명확하고 쉽다.
        Map<String,Integer> DNA = new HashMap<>();
        List<String> result = new ArrayList<>();
        for(int i=0;i<s.length()-9;i++){
            String dna = s.substring(i,i+10);//끝 인덱스는 포함하지 않으니까.
            if(DNA.containsKey(dna)){
                int val = DNA.get(dna); 
                DNA.put(dna,++val);
            }else{
                DNA.put(dna,1);
            }
        }
        for(Map.Entry<String,Integer> item : DNA.entrySet()){
            if(item.getValue()>1){
                result.add(item.getKey());
            }
        }
        return result;
    }
}

다른 풀이 방법

• Constraints에서 s 길이 보고, 그 이상이나 이하면 바로 return 해줬다.

public List<String> findRepeatedDnaSequences(String s) {
    if( s.length() >=100000 || s.length() <11)
        return new ArrayList<>();
    Set<String> set = new HashSet<>();
    Set<String> res = new HashSet<>();
    int LETTER_LENGTH = 10;
    for (int i = 0; i < s.length() - LETTER_LENGTH + 1; i++) {
        String key = s.substring(i, i + LETTER_LENGTH);
        if (!set.contains(key)) {
            set.add(key);
        } else {
            res.add(key);
        }
    }
    return new ArrayList<>(res);
}
}

• 키가 존재하면 반복되는거니까 바로 repeated 어레이에 넣어줬다.

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashSet seen = new HashSet();
        HashSet repeated = new HashSet();

        for(int i = 0; i + 9 < s.length(); i++) {
            String ten = s.substring(i, i + 10);
            if (seen.contains(ten))
                repeated.add(ten);
            else
                seen.add(ten);
        }

        return new ArrayList(repeated);
    }
}