187. Repeated DNA Sequences

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

For example, "ACGAATTCCG" is a DNA sequence.

When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

Constraints:

1 <= s.length <= 10⁵
s[i] is either 'A', 'C', 'G', or 'T'.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)String (Chuỗi)

⏱️ Thời gian O(n²)

💾 Không gian O(n)

💻 Lời Giải

C++ 0187-repeated-dna-sequences.cpp

using ll = long long;
const ll base = 4;
const ll mod = 1e9 + 7;
const ll limit = 9;

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int n = (int)s.size();
        if (n < 10) {
            return {};
        }
        vector<ll> h(n + 1, 0);
        vector<ll> p(n + 1, 1);
        unordered_map<char, int> codes;
        string DNA = "ACGT";
        for (int i = 0; i < (int)DNA.size(); ++i) {
            codes[DNA[i]] = i;
        }
        for (int i = 1; i <= n; ++i) {
            h[i] = (h[i - 1]*base + codes[s[i - 1]]) % mod;
            p[i] = (p[i - 1]*base) % mod;
        }
        unordered_map<int, int> um;
        vector<string> ans;
        for (int i = 1; i <= n - limit; ++i) {
            int l = i;
            int r = i + limit;
            if (++um[(h[r] - h[l - 1]*p[r - l + 1] + mod*mod) % mod] == 2) {
                ans.push_back(s.substr(l - 1, r - l + 1));
            }
        }
        return ans;
    }
};