Problema
Todo el ADN está compuesto por una serie de nucleótidos abreviados como A, C, G y T, por ejemplo: «ACGAATTCCG». Al estudiar el ADN, a veces es útil identificar secuencias repetidas dentro del ADN.
Escribe una función para encontrar todas las secuencias de 10 letras (subcadenas) que ocurren más de una vez en una molécula de ADN.
Por ejemplo, dado s = «AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT», devuelve: [«AAAAACCCCC», «CCCCCAAAAA»].
Solución Java
La clave para resolver este problema es que cada uno de los 4 nucleótidos se puede almacenar en 2 bits. Por lo tanto, la secuencia de 10 letras se puede convertir en un número entero de 20 bits. La siguiente es una solución de Java. Puede usar un ejemplo para ejecutar manualmente el programa y ver cómo funciona.
public List<String> findRepeatedDnaSequences(String s) { List<String> result = new ArrayList<>(); if(s==null||s.length()<10){ return result; } HashMap<Character, Integer> dict = new HashMap<>(); dict.put('A', 0); dict.put('C', 1); dict.put('G', 2); dict.put('T', 3); int hash=0; int mask = (1<<20) -1; HashSet<Integer> added = new HashSet<>(); HashSet<Integer> temp = new HashSet<>(); for(int i=0; i<s.length(); i++){ hash = (hash<<2) + dict.get(s.charAt(i)); if(i>=9){ hash&=mask; if(temp.contains(hash) && !added.contains(hash)){ result.add(s.substring(i-9, i+1)); added.add(hash); } temp.add(hash); } } return result; } |
