Memory Limited???


  • 0
    M
     public static ArrayList<String> findRepeatedDnaSequences(String s) {
            ArrayList<String> res=new ArrayList<String>();
            if(s==null||s.length()<11)
            return res;
            
            HashSet<String> set=new HashSet<String>();
            StringBuffer sb=new StringBuffer();
            for(int i=0;i<10;i++){
                sb.append(s.charAt(i));
            }
            
            String temp=sb.toString();
            set.add(temp);
            
            for(int i=10;i<s.length();i++){
                sb.deleteCharAt(0);
                sb.append(s.charAt(i));
                if(set.contains(sb.toString())){
                    res.add(sb.toString());
                }else{
                    set.add(sb.toString());
                }
            }
            return res;
        }

  • 0
    J

    I guess the memory limitation comes from the size of your key. it's a string with length 10, which means at least 10 byte. That means if you would have 4^10 at most different keys, which will be 10*4^10B=10MB key only.


  • 0
    M

    So, what's your suggestion? Thank you!


  • 0
    C

    I am not sure if it has anything to do with the memory problem you are having but your code will probably add the same substring to res multiple times. Let's say if the substring exists 5 times, it will be added to res 4 times.


  • 6
    D

    Few days ago, your solution should be accepted. However, recently Leetcode changed the memory limit on this problem. So you need to find a way to do the hashing.

    The idea is to convert the string into integer, then just use this integer as the key for HashMap. It will reduce memory used.

    So let say: 'A' -> 0, 'C' -> 1, 'G' ->2, 'T' -> 3 (since the DNA sequence contains only A, C, G, T). in the code below, the getV function is to get the integer value of a string based on the character mapping explained before.

    Code:

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> list = new LinkedList<String>();
        HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i = 0; i<s.length()-9; i++){
            int v = getV(s, i);
            if(!map.containsKey(v))
                map.put(v, false);
            else{
                if(map.get(v) == false){
                    list.add(s.substring(i, i+10));
                    map.put(v, true);
                }  
            }
        }
        return list;
    }
    private int getV(String s, int index){
        int v = 0;
        for(int i = index; i<index+10; i++){
            int vv = 0;
            if(s.charAt(i) == 'A') vv = 0;
            else if(s.charAt(i) == 'C') vv = 1;
            else if(s.charAt(i) == 'G') vv = 2;
            else vv = 3;
            v <<= 2;
            v |= vv;
        }
        return v;
    }

  • 0
    U

    I used this way, but still get Memory limited...


  • 0
    D

    what is your code. My above code is still accepted ^_^


  • 0
    D

    Why did you shift the bit sequence by 2? How did you decide on that number?


  • 0
    P

    My Solution just like yours, but always got "Output Limit Exceeded", I used a "unordered_map<int, int>". It's a map from a integer to another integer.


Log in to reply
 

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