Help! Memory limit exceed


  • 1
    P

    I submit below solution, but failed as 'memory limit exceed'. It didn't say which testcase has problem. Could someone help to take a look? Thanks!!

    `

        public List<String> findRepeatedDnaSequences(String s) {
    	List<String> retList = new ArrayList<String>();
    	if (s == null || s.length() == 0 || s.length() < 10)
    	 return retList;
    
    	Set<String> seqSet = new HashSet<String>();
    	int i = 0;
    	while (i + 10 < s.length()) {
    		String sequence = s.substring(i, i + 10);
    		if (!seqSet.contains(sequence)) {
    			seqSet.add(sequence);
    		} else {
    			retList.add(sequence);
    		}
    		i++;
    	}
    
    	return retList;
    }`

  • 0
    C

    because you are storing each possible string, and, if one string appears 10 times, it will be added into the output 9 times.


  • -5
    D
    This post is deleted!

  • 3
    F

    This actually implies that we should not use Set to solve it. And we can find from the tag that bit manipulation is expected to be used. So, just try to set flags using bit manipulation to replace Set or Map.


  • 0
    C

    I met the same problem. the tag of this problem is "bit manipulation", and the DNA sequence is 10-letter. Think about it! In order to save memory, try to use integer instead of string as key in hash table.


  • -1
    Y

    There is another problem, the result of your code have redundant sequences.


  • 0
    Z
    This post is deleted!

Log in to reply
 

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