โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

นับลำดับซ้ำต่อเนื่องสั้นใน DNA (STR)

สำหรับแต่ละหน่วยซ้ำสั้น ให้หาจำนวนครั้งที่ซ้ำติดกันยาวที่สุดในลำดับ DNA

สิ่งที่คุณจะได้เรียนรู้

  • เปรียบเทียบสตริงย่อยกับรูปแบบที่กำหนด
  • นับจำนวนครั้งที่ซ้ำติดกันโดยเริ่มจากตำแหน่งหนึ่ง
  • เก็บจำนวนที่ดีที่สุดของแต่ละรูปแบบ

โจทย์

ห้องแล็บนิติวิทยาศาสตร์เปรียบเทียบบุคคลด้วยลำดับซ้ำต่อเนื่องสั้น (short tandem repeats หรือ STR) ซึ่งเป็นหน่วย DNA สั้น ๆ เช่น AGAT ที่ปรากฏซ้ำติดกันหลายครั้ง สำหรับแต่ละหน่วย ห้องแล็บจะบันทึกจำนวนครั้งที่ซ้ำติดกันยาวที่สุดในลำดับ ใน TTAGATAGATAGATCAGATAGAT หน่วย AGAT ปรากฏติดกันสามครั้งช่วงต้น และสองครั้งในภายหลัง จำนวนของมันจึงเป็น 3

จงเขียน dna_str_count(sequence, repeats)

อินพุต

sequence: ลำดับ DNA ที่ประกอบด้วยตัวอักษร A, C, G และ T

repeats: หน่วย STR ที่ต้องการวัด

เอาต์พุต

คืนค่าจำนวนหนึ่งค่าต่อหนึ่งหน่วย เรียงตามลำดับเดียวกับ repeats โดยเป็นจำนวนครั้งมากที่สุดที่หน่วยนั้นปรากฏติดกัน หน่วยที่ไม่ปรากฏเลยมีค่าเป็น 0

เงื่อนไข

0 ≤ ความยาวของ sequence ≤ 5,000

1 ≤ จำนวนหน่วย ≤ 10

แต่ละหน่วยมีตัวอักษร 1 ถึง 8 ตัว

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]

ผลลัพธ์ที่คาดหวัง:
expected = [3, 1]
อินพุต:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {3, 1};
อินพุต:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {3, 1};

คำอธิบาย

AGAT ซ้ำติดกัน 3 ครั้งที่ต้นลำดับ และเพียง 2 ครั้งที่ท้าย จึงได้ 3 ส่วน CA ปรากฏครั้งเดียว จึงได้ 1

ตัวอย่างที่ 2
อินพุต:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]

ผลลัพธ์ที่คาดหวัง:
expected = [3, 1, 0]
อินพุต:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {3, 1, 0};
อินพุต:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {3, 1, 0};

คำอธิบาย

AATG ซ้ำ 3 ครั้ง TATC ปรากฏครั้งเดียว และ GATA ไม่ปรากฏเลย ได้ [3, 1, 0]

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

จากตำแหน่งเริ่มต้น ให้กระโดดไปข้างหน้าทีละความยาวของหน่วย ตราบใดที่ชิ้นถัดไปยังเหมือนกับหน่วยนั้น

คำใบ้ 2

ลองทุกตำแหน่งเริ่มต้น แล้วจำช่วงที่ยาวที่สุดไว้

คำใบ้ 3

หน่วยที่ไม่เคยตรงเลยจะทำให้จำนวนที่ดีที่สุดยังเป็น 0

ความซับซ้อนที่คาดหวัง

เวลา O(n × m × k), หน่วยความจำเพิ่ม O(m)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก