LeetCode DNA 중복 시퀀스

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

모든 DNA 는 'ACGAATTCCG' 와 같은 A, C, G, T 로 표시 되 는 뉴 클 레오 티 드 서열 로 구성 된다.우 리 는 DNA 를 배 울 때 DNA 에서 중복 서열 을 식별 하 는 것 이 중요 하 다.
함수 하 나 를 써 서 여러 번 나 타 났 고 10 개의 영문 자 모 를 포함 하 는 하위 서열 을 찾 아야 합 니 다.
//
분석, 가장 직접적인 방법 은 모든 길이 가 10 인 하위 서열 을 기록 하기 위해 HashTable 을 만 드 는 것 이다.
그룹 후 출력 횟수 가 1 보다 많 습 니 다.
그러나 leetcode 를 통과 할 수 없 는 이 유 는 메모리 제한 을 초과 한 것 입 니 다.

public List findRepeatedDnaSequences(String s) {
        List list = new ArrayList();
        if(s == null || s.length() < 10) return list;
        
        HashMap table = new HashMap();
        int L = 10;
        for(int i = 0; i <= s.length() - L; i++){
            String sub = s.substring(i, i + L);
            if(table.containsKey(sub)){
                table.put(sub, table.get(sub) + 1);
            }else table.put(sub, 1);
        }
        
        Iterator it = table.keySet().iterator();
        while(it.hasNext()){
            String key = it.next();
            if(table.get(key) > 1)
                list.add(key);
        }
        return list;
    }

개선 방안:
1. 첫 번 째 출력 List 는 ArrayList 가 아 닌 LinkedList 로 바 꿉 니 다.
2. HashMap 의 Key 는 길이 가 string 이다. 즉, 그 가 차지 하 는 메모리 크기 는 약 2 * 10 바이트 이다.계속 분석 해 보 니 모든 문자열 은 네 개의 서로 다른 문자 (A, C, G, T) 만 포함 되 어 있 고 우 리 는 2 bit 로 표시 할 수 있 습 니 다.이렇게 하면 문자열 을 하나의 정수 공간 에 비 추 는 것 을 자 연 스 럽 게 생각 할 수 있 습 니 다. 왜냐하면 모든 문자열 은 유일 하 게 2 * 10 bit 로 표시 할 수 있 기 때 문 입 니 다.
3. HashMap 의 값 Value 도 Boolean (1bit 만) 으로 바 꿀 수 있 습 니 다.
다음은 수 정 된 알고리즘 이다.

private int myHash(String s){
        int n = 0;
        for(int i = 0; i < s.length(); i++){
                n <<=2;
                char c = s.charAt(i);
                if(c == 'C'){
                    n += 1;
                }else if(c == 'G'){
                    n += 2;
                }else if(c == 'T'){
                    n += 3;
                }
        }
        return n;
    }
    
    public List findRepeatedDnaSequences(String s) {
        List list = new LinkedList();
        if(s == null || s.length() < 10) return list;

        HashMap table = new HashMap();
        int L = 10;
        for(int i = 0; i <= s.length() - L; i++){
            String sub = s.substring(i, i + L);
            int hs = myHash(sub);
            if(table.containsKey(hs)){
                if(!table.get(hs)) list.add(sub);
                table.put(hs, true);
            }else{
                table.put(hs, false);
            }
        }
        return list;
    }