Сложность: medium
ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.
Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.
Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке.
Пример:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]
👨💻 Алгоритм:
1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):
Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].
В противном случае вычисляем скользящий хеш из предыдущего значения хеша.
2⃣Проверяем хеш в хешсете:
Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод.
В противном случае добавляем хеш в хешсет.
3⃣Возвращаем список вывода, содержащий все повторяющиеся последовательности.
😎 Решение:
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
int L = 10, n = s.length();
if (n <= L) return new ArrayList();
int a = 4, aL = (int) Math.pow(a, L);
Map<Character, Integer> toInt = new HashMap() {
{
put('A', 0);
put('C', 1);
put('G', 2);
put('T', 3);
}
};
int[] nums = new int[n];
for (int i = 0; i < n; ++i) nums[i] = toInt.get(s.charAt(i));
int h = 0;
Set<Integer> seen = new HashSet();
Set<String> output = new HashSet();
for (int start = 0; start < n - L + 1; ++start) {
if (start != 0) h = h * a -
nums[start - 1] * aL +
nums[start + L - 1];
else for (int i = 0; i < L; ++i) h = h * a + nums[i];
if (seen.contains(h)) output.add(s.substring(start, start + L));
seen.add(h);
}
return new ArrayList<String>(output);
}
}Ставь 👍 и забирай 📚 Базу знаний