Problème
Comparez deux chaînes d'ADN position par position et comptez les différences. Seuls les caractères à la même position sont comparés ; il ne faut ni insérer, ni supprimer, ni décaler de caractères. Aucune connaissance en biologie n'est requise.
Implémentez hamming_distance(first, second).
Entrée
first : La première chaîne d'ADN.
second : La seconde chaîne d'ADN, de même longueur que la première.
Sortie
Retournez le nombre de positions où les caractères diffèrent.
Contraintes
Les deux chaînes ont la même longueur, comprise entre 0 et 100 000. Les caractères sont des lettres majuscules A, C, G ou T.
Exemples
Entrée :
first = "ACCT"
second = "AGCA"
Sortie attendue :
expected = 2Entrée :
std::string first = "ACCT";
std::string second = "AGCA";
Sortie attendue :
long long expected = 2;Entrée :
string first = "ACCT";
string second = "AGCA";
Sortie attendue :
long expected = 2;Explication
La deuxième position est C contre G et la quatrième est T contre A. Les première et troisième positions correspondent : il y a donc deux différences.
Entrée :
first = "GATT"
second = "GATT"
Sortie attendue :
expected = 0Entrée :
std::string first = "GATT";
std::string second = "GATT";
Sortie attendue :
long long expected = 0;Entrée :
string first = "GATT";
string second = "GATT";
Sortie attendue :
long expected = 0;Explication
Les quatre positions correspondent, donc aucune différence n'est comptée.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Comparez les deux chaînes position par position et comptez chaque caractère différent.
Indice 2
Un seul passage avec une itération par paires suffit ; pas besoin de réordonner ni de chercher des sous-chaînes.
Indice 3
N’oubliez pas que des entrées de même longueur peuvent être vides, ce qui doit donner zéro différence.
Complexité attendue
temps O(n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.