Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Đếm đoạn lặp ngắn liền kề (STR) trong DNA

Với mỗi đoạn lặp ngắn liền kề, tìm số bản sao nối tiếp nhau nhiều nhất trong một chuỗi DNA.

Bạn sẽ học được gì

  • So sánh một chuỗi con với một mẫu
  • Đếm số bản sao nối tiếp bắt đầu từ một vị trí
  • Lưu số đếm tốt nhất cho từng mẫu

Đề bài

Xem bản gốc (English)

Các phòng giám định pháp y so sánh người với nhau dựa vào các đoạn lặp ngắn liền kề (short tandem repeat, STR): những đơn vị DNA ngắn như AGAT xuất hiện nhiều lần liên tiếp. Với mỗi đơn vị, phòng thí nghiệm ghi lại số bản sao liên tiếp nhiều nhất ở bất kỳ đâu trong chuỗi. Trong TTAGATAGATAGATCAGATAGAT, đơn vị AGAT lặp ba lần liên tiếp gần đầu chuỗi và hai lần ở phía sau, nên số đếm của nó là 3.

Hãy viết dna_str_count(sequence, repeats).

Đầu vào

sequence: Chuỗi DNA, chỉ gồm các chữ cái A, C, G và T.

repeats: Các đơn vị STR cần đo.

Đầu ra

Trả về một số đếm cho mỗi đơn vị, theo đúng thứ tự trong repeats: số bản sao nối tiếp nhau nhiều nhất. Đơn vị nào không xuất hiện thì có số đếm 0.

Ràng buộc

0 ≤ độ dài sequence ≤ 5,000

1 ≤ số đơn vị ≤ 10

Mỗi đơn vị có từ 1 đến 8 chữ cái

Ví dụ

Ví dụ 1
Đầu vào:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]

Kết quả mong đợi:
expected = [3, 1]
Đầu vào:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};

Kết quả mong đợi:
std::vector<long long> expected = {3, 1};
Đầu vào:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};

Kết quả mong đợi:
long[] expected = new long[] {3, 1};

Giải thích

AGAT lặp 3 lần ở đầu và chỉ 2 lần ở cuối nên được 3; CA xuất hiện một lần nên được 1.

Ví dụ 2
Đầu vào:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]

Kết quả mong đợi:
expected = [3, 1, 0]
Đầu vào:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};

Kết quả mong đợi:
std::vector<long long> expected = {3, 1, 0};
Đầu vào:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};

Kết quả mong đợi:
long[] expected = new long[] {3, 1, 0};

Giải thích

AATG lặp 3 lần, TATC một lần và GATA không lần nào: [3, 1, 0].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Từ một vị trí bắt đầu, cứ nhảy tới một đoạn bằng độ dài đơn vị chừng nào đoạn tiếp theo còn trùng với đơn vị.

Gợi ý 2

Thử mọi vị trí bắt đầu và ghi nhớ dãy dài nhất.

Gợi ý 3

Đơn vị nào không khớp lần nào thì số đếm tốt nhất vẫn là 0.

Độ phức tạp mong đợi

thời gian O(n × m × k), bộ nhớ phụ O(m)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.