Problem
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.
Einschränkungen
Both strings have the same length, from 0 to 100,000. Characters are uppercase A, C, G, or T.
Beispiele
Eingabe:
first = "ACCT"
second = "AGCA"
Erwartete Ausgabe:
expected = 2Eingabe:
std::string first = "ACCT";
std::string second = "AGCA";
Erwartete Ausgabe:
long long expected = 2;Eingabe:
string first = "ACCT";
string second = "AGCA";
Erwartete Ausgabe:
long expected = 2;Erläuterung
The second position is C versus G and the fourth is T versus A. The first and third match: two differences.
Eingabe:
first = "GATT"
second = "GATT"
Erwartete Ausgabe:
expected = 0Eingabe:
std::string first = "GATT";
std::string second = "GATT";
Erwartete Ausgabe:
long long expected = 0;Eingabe:
string first = "GATT";
string second = "GATT";
Erwartete Ausgabe:
long expected = 0;Erläuterung
All four positions match, so no differences are counted.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Vergleiche beide Strings Position für Position und zähle, wenn sich die Zeichen unterscheiden.
Hinweis 2
Ein einziger Durchlauf mit gepaarten Iterationen reicht; Umordnen oder Teilstringsuchen ist nicht nötig.
Hinweis 3
Denk daran: Gleich lange Eingaben können trotzdem leer sein, dann gibt es null Unterschiede.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.