Not fast or short.


  • 0
    F

    Because of the memory problem I converted the Strings to base 4 integers.

    public class Solution {
        public List<String> findRepeatedDnaSequences(String s) {
            HashSet<Integer> tenNucleotides = new HashSet<Integer>();
            HashSet<Integer> repetitions = new HashSet<Integer>();
            int dnasubstrint;
            for (int i = 0; i < s.length()-9; i++) {
                dnasubstrint = dna2int(s.substring(i,i+10));
                if (!tenNucleotides.add(dnasubstrint))
                    repetitions.add(dnasubstrint);
            }
            
            List<String> result = new LinkedList<String>();
            Iterator<Integer> iter = repetitions.iterator();
            while (iter.hasNext()) {
                result.add(int2dna(iter.next()));
            }
            return result;
        }
        
        public int dna2int(String s) {
            int i = 0;
            for (int j = 0; j < s.length(); j++) {
                i += Math.pow(4,j)*nuc2int(s.charAt(j));
            }
            return i;
        }
        
        public String int2dna(int i) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < 10; j++) {
                sb.append(int2nuc(i % 4));
                i /= 4;
            }
            return sb.toString();
        }
        
        public char int2nuc(int i) {
            switch (i) {
                case 0: return 'A';
                case 1: return 'C';
                case 2: return 'G';
                case 3: return 'T';
            }
            return 'X';
        }
        
        public int nuc2int(char c) {
            switch (c) {
                case 'A': return 0;
                case 'C': return 1;
                case 'G': return 2;
                case 'T': return 3;
            }
            return -1;
        }
    }

Log in to reply
 

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