It shows as MLE but I am not sure why.


  • 0
    L
    public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        if (s == null || s.length() < 10) return new ArrayList<>();
        Map<Character, Integer> dict = new HashMap<>();
        dict.put('A', 1);
        dict.put('C', 2);
        dict.put('G', 3);
        dict.put('T', 4);
        final int bitMask = (1 << 20) - 1;
        
        Set<Integer> seen = new HashSet<>();
        List<String> ans = new ArrayList<>();
        Set<Integer> found = new HashSet<>();
        int code = encode (s.substring(0, 10), dict);
        seen.add(code);
        
        for (int i = 10; i < s.length(); i++) {
            code = (code << 2) & bitMask;
            code |= dict.get(s.charAt(i));
            
            if (found.contains(code)) continue;
            if (seen.contains(code)){
                ans.add(s.substring(i - 10 + 1, i + 1));
                found.add(code);
            } else {
                seen.add(code);
            }
        }
        return ans;
    }
    
    private int encode(String s, Map<Character, Integer> dict) {
        int code = 0;
        for (int i = 0; i < s.length(); i++) {
            code <<= 2;
            code |= dict.get(s.charAt(i));
        }
        return code;
    }
    

    }


Log in to reply
 

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