Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Hamming Distance

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

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

  • So sánh hai chuỗi theo từng vị trí
  • Đếm số chỗ khác nhau
  • Kiểm tra độ dài bằng nhau

Đề 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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

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.