Problema
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.
Vincoli
Both strings have the same length, from 0 to 100,000. Characters are uppercase A, C, G, or T.
Esempi
Input:
first = "ACCT"
second = "AGCA"
Output atteso:
expected = 2Input:
std::string first = "ACCT";
std::string second = "AGCA";
Output atteso:
long long expected = 2;Input:
string first = "ACCT";
string second = "AGCA";
Output atteso:
long expected = 2;Spiegazione
The second position is C versus G and the fourth is T versus A. The first and third match: two differences.
Input:
first = "GATT"
second = "GATT"
Output atteso:
expected = 0Input:
std::string first = "GATT";
std::string second = "GATT";
Output atteso:
long long expected = 0;Input:
string first = "GATT";
string second = "GATT";
Output atteso:
long expected = 0;Spiegazione
All four positions match, so no differences are counted.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Confronta le due stringhe una posizione alla volta e conta quando i caratteri differiscono.
Suggerimento 2
Basta un solo passaggio con iterazione in coppia; non servono riordini né ricerche di sottostringhe.
Suggerimento 3
Ricorda che input della stessa lunghezza possono anche essere vuoti, e in quel caso le differenze sono zero.
Complessità attesa
tempo O(n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.