ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Hamming Distance

Compare two DNA strings position by position and count the differences.

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

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

โจทย์

Compare two DNA strings position by position and count the differences. Only characters at the same position are compared; do not insert, delete, or shift characters. No biology knowledge is needed.

Implement hamming_distance(first, second).

Input

first: The first DNA string.

second: The equal-length second DNA string.

Output

Return the number of positions with different characters.

เงื่อนไข

Both strings have the same length, from 0 to 100,000. Characters are uppercase A, C, G, or T.

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
first = "ACCT"
second = "AGCA"

ผลลัพธ์ที่คาดหวัง:
expected = 2
อินพุต:
std::string first = "ACCT";
std::string second = "AGCA";

ผลลัพธ์ที่คาดหวัง:
long long expected = 2;
อินพุต:
string first = "ACCT";
string second = "AGCA";

ผลลัพธ์ที่คาดหวัง:
long expected = 2;

คำอธิบาย

The second position is C versus G and the fourth is T versus A. The first and third match: two differences.

ตัวอย่างที่ 2
อินพุต:
first = "GATT"
second = "GATT"

ผลลัพธ์ที่คาดหวัง:
expected = 0
อินพุต:
std::string first = "GATT";
std::string second = "GATT";

ผลลัพธ์ที่คาดหวัง:
long long expected = 0;
อินพุต:
string first = "GATT";
string second = "GATT";

ผลลัพธ์ที่คาดหวัง:
long expected = 0;

คำอธิบาย

All four positions match, so no differences are counted.

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

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

คำใบ้ 1

เปรียบเทียบทั้งสองสตริงทีละตำแหน่ง แล้วนับตอนที่ตัวอักษรต่างกัน

คำใบ้ 2

วนครั้งเดียวแบบจับคู่ตำแหน่งก็พอ ไม่ต้องสลับลำดับหรือค้นหาซับสตริง

คำใบ้ 3

อย่าลืมว่าข้อมูลยาวเท่ากันก็อาจว่างได้ ซึ่งควรได้ผลต่างเป็นศูนย์

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

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

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

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

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

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

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