Why does this Java solution exceed memory limit?


  • 0
    R

    I am using a BitSet, and rolling hash for this one, still getting the exceed memory limit error.
    What did I miss here?
    Thanks.

    public List<String> findRepeatedDnaSequences(String s) {
        int k = 10;
        List<String> res = new ArrayList<String>();
        if(s==null){return res;}
        int len = s.length();
        if(len<k){
            return res;
        }
        BitSet visited = new BitSet(1<<20);
        StringBuilder dna = new StringBuilder(s.substring(0, k));
        int code = getCode(dna);
        visited.set(code);
        res.add(dna.toString());
        for(int i=k;i<len;i++){ //i is the next char index
            int nextCode = updateCode(code, dna.charAt(0), s.charAt(i));
            dna.deleteCharAt(0).append(s.charAt(i));
            if(!visited.get(nextCode)){
            	visited.set(nextCode);
                res.add(dna.toString());
            }
            code = nextCode;
        }
        return res;
    }
    
    private int getCode(char c){
        switch(c){
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
            default: 
                throw new IllegalArgumentException("Unknown char:" + c);
        }
    }
    
    private int getCode(StringBuilder dna){
        int code = 0;
        for(int i=0; i<dna.length(); i++){ //length is always 10
            code = (code << 2) + getCode(dna.charAt(i));
        }
        return code;
    }
    
    private int updateCode(int code, char remove, char c){
        code -= getCode(remove)*1<<18; //4^(10-1) = 4^(9) = 2^18
        code<<=2; //code *4
        code+=getCode(c);
        return code;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.