Tried my best to use less memory, but still Memory Limit Exceeded


  • 0
    W
    public class Solution {
    private final int A = 0x00_00_00_01;
    private final int C = 0x00_00_00_02;
    private final int G = 0x00_00_00_03;
    private final int T = 0x00_00_00_04;
    
    public List<String> findRepeatedDnaSequences(String s) {
    	return findRepeatedDnaSequences(s, 10);
    }
    
    public List<String> findRepeatedDnaSequences(String s, int subLength) {
    	List<String> result = new ArrayList<String>();
    	Set<Integer> processor = new HashSet<Integer>();
    	int length = s.length();
    
    	if(length <= subLength)
    		return result;
    
    	for(int i=0; i<=length - subLength; i++){
    		String subString = s.substring(i, i + subLength);
    		int tempResult = 0;
    		for(int j=0; j<subLength; j++){
    			int letter = 0;
    			switch(s.charAt(i+j)){
    			case 'A':
    				letter = A;
    				break;
    			case 'C':
    				letter = C;
    				break;
    			case 'G':
    				letter = G;
    				break;
    			case 'T':
    				letter = T;
    			}
    			tempResult = tempResult << 2;
    			tempResult |= letter;
    		}
    		if(processor.contains(tempResult))
    			result.add(subString);
    		else
    			processor.add(tempResult);
    	}
    	processor.clear();
    	return result;
    }
    

    }


  • 1
    D

    Try using "result = new LinkedList<String>()" instead of ArrayList, that will decrease memory usage approximately by factor of 1.5-2, instead of HashSet for storing hash values, use simply byte array, this will decrease your memory usage approximately by factory of 8.
    Hope this helps.


Log in to reply
 

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