Đề bài
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.
Ràng buộc
Both strings have the same length, from 0 to 100,000. Characters are uppercase A, C, G, or T.
Ví dụ
Đầu vào:
first = "ACCT"
second = "AGCA"
Kết quả mong đợi:
expected = 2
Đầu vào:
std::string first = "ACCT";
std::string second = "AGCA";
Kết quả mong đợi:
long long expected = 2;
Đầu vào:
string first = "ACCT";
string second = "AGCA";
Kết quả mong đợi:
long expected = 2;
Giải thích
The second position is C versus G and the fourth is T versus A. The first and third match: two differences.
Đầu vào:
first = "GATT"
second = "GATT"
Kết quả mong đợi:
expected = 0
Đầu vào:
std::string first = "GATT";
std::string second = "GATT";
Kết quả mong đợi:
long long expected = 0;
Đầu vào:
string first = "GATT";
string second = "GATT";
Kết quả mong đợi:
long expected = 0;
Giải thích
All four positions match, so no differences are counted.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
So sánh hai chuỗi từng vị trí một và đếm khi ký tự khác nhau.
Gợi ý 2
Chỉ cần duyệt một lần với cặp phần tử tương ứng; không cần hoán đổi hay tìm kiếm chuỗi con.
Gợi ý 3
Nhớ rằng đầu vào cùng độ dài vẫn có thể rỗng, khi đó số khác nhau là zero.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
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.