Is the memory limit too strict?


  • 0
    H

    Is current limit put on memory too strict?
    My previous AC solution is not AC anymore due to MLE.
    I checked other's AC solution, like this one. I found it uses the exact same algorithm that I used before.
    I believe even this AC solution is barely passing the test, since it will get MLE after even a small change.
    For example: replace"Set" to the "HashSet" in first two lines or use an extra variable to hold temp substring (DNA sequence with len 10), etc.

    I believe the algorithm is correct, so I doubt whether the limit put on memory is too strict

    Below is my old AC solution which now get MLT:

    public int Char2Int(Character c){
        //ATCG can be differentiated by 2 bits
        switch (c){
            case 'A':
               return 0;
            case 'T':
                return 1;
            case 'C':
                return 2;
            case 'G':
                return 3;
        }
        
        return -1;
    }
    
    public int getCode(String s){
        int code = 0;
        for(int i = 0; i < s.length(); i++){
            code <<= 2;
            code |= Char2Int(s.charAt(i));
        }
        return code;
    }
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        //why not use hashSet? Because we may have a match strings appear more than 2 times, we only need it once
        HashMap<Integer, Boolean> hs = new HashMap<Integer, Boolean>();
        if(s == null || s.length() < 10) return result;
        
        for(int i = 0; i + 9 < s.length(); i++){
            String sub = s.substring(i, i+10);//end of substring is exclusive
            int code = getCode(sub);
            if(hs.containsKey(code)){
                if(!hs.get(code)){//if it is the second time visit this code
                    result.add(sub);
                    hs.put(code, true);//set to true to prevent further visit
                }
            }else{
                hs.put(code, false);
            }
        }
        
        return result;
    }
    

  • 0

    Please try submitting again, I have removed the memory limit on the judge side.


Log in to reply
 

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