Another java solution


  • 0
    F
        public List<String> findRepeatedDnaSequences(String s) {
            int n = s.length();
            ArrayList<String> result = new ArrayList<>();
            if (n <= 10) {
                return result;
            }
            Map<Integer, Integer> map = new HashMap<>();
            String DNA = "ACGT";
            int previous = 0, current = 0;
            for (int i = 0; i < 10; i++) {
                previous |= (DNA.indexOf(s.charAt(i)) << (18 - 2 * i));
            }
            map.put(previous, 1);
            for (int i = 10; i < n; i++) {
                current = previous;
                current &= ~(3 << 18);
                current <<= 2;
                current |= DNA.indexOf(s.charAt(i));
                previous = current;
                map.merge(previous, 1, (x, y) -> x + y);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() > 1) {
                    StringBuilder stringBuilder = new StringBuilder();
                    int key = entry.getKey();
                    for (int i = 18; i >= 0; i -= 2) {
                        stringBuilder.append(DNA.charAt((key >> i) & 3));
                    }
                    result.add(stringBuilder.toString());
                }
            }
            return result;
        }

Log in to reply
 

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