187. Repeated DNA Sequences

public class Solution {
    public IList<string> FindRepeatedDnaSequences(string s) {
        int L = 10, n = s.Length;
        if (n <= L) return new List<string>();
        int a = 4, aL = (int)Math.Pow(a, L);
        Dictionary<char, int> toInt = new Dictionary<char, int>{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        int[] nums = s.Select(c => toInt[c]).ToArray();
        int h = 0;
        HashSet<int> seen = new HashSet<int>();
        HashSet<string> output = new HashSet<string>();
        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, L));
            seen.Add(h);
        }
        return output.ToList();
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<string> FindRepeatedDnaSequences(string s) {
        int L = 10, n = s.size();
        if (n <= L) return new List<string>();
        int a = 4, aL = (int)Math.Pow(a, L);
        unordered_map<char, int> toInt = new unordered_map<char, int>{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        vector<int>& nums = s.Select(c => toInt[c]).ToArray();
        int h = 0;
        HashSet<int> seen = new HashSet<int>();
        HashSet<string> output = new HashSet<string>();
        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.push_back(s.Substring(start, L));
            seen.push_back(h);
        }
        return output.ToList();
    }
}

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);
    }
}

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        L, n = 10, len(s)
        if n <= L:
            return []
        a = 4
        aL = pow(a, L)
        to_int = {"A": 0, "C": 1, "G": 2, "T": 3}
        nums = [to_int.get(s[i]) for i in range(n)]

        h = 0
        seen, output = set(), set()
        for start in range(n - L + 1):
            if start != 0:
                h = h * a - nums[start - 1] * aL + nums[start + L - 1]
            else:
                for i in range(L):
                    h = h * a + nums[i]
            if h in seen:
                output.add(s[start : start + L])
            seen.add(h)
        return output

Algorithm

1️⃣

Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):

Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].

В противном случае вычисляем скользящий хеш из предыдущего значения хеша.

2️⃣

Проверяем хеш в хешсете:

Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод.

В противном случае добавляем хеш в хешсет.

3️⃣

Возвращаем список вывода, содержащий все повторяющиеся последовательности.

😎