Distancia de Hamming entre dos cuerdas

Se le dan dos strings de igual longitud, debe encontrar la distancia de Hamming entre estas strings. 
Donde la distancia de Hamming entre dos strings de igual longitud es el número de posiciones en las que el carácter correspondiente es diferente. 

Ejemplos: 

Input : str1[] = "geeksforgeeks", str2[] = "geeksandgeeks"
Output : 3
Explanation : The corresponding character mismatch are highlighted.
"geeksforgeeks" and "geeksandgeeks"

Input : str1[] = "1011101", str2[] = "1001001"
Output : 2
Explanation : The corresponding character mismatch are highlighted.
"1011101" and "1001001"

Este problema se puede resolver con un enfoque simple en el que atravesamos las strings y contamos el desajuste en la posición correspondiente. La forma extendida de este problema es la distancia de edición.

Algoritmo: 

int hammingDist(char str1[], char str2[])
{
    int i = 0, count = 0;
    while(str1[i]!='\0')
    {
        if (str1[i] != str2[i])
            count++;
        i++;
    }
    return count;
}

A continuación se muestra la implementación de dos strings. 

C++

// C++ program to find hamming distance b/w two string
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate Hamming distance
int hammingDist(string str1, string str2)
{
    int i = 0, count = 0;
    while (str1[i] != '\0') {
        if (str1[i] != str2[i])
            count++;
        i++;
    }
    return count;
}
 
// driver code
int main()
{
    string str1 = "geekspractice";
    string str2 = "nerdspractise";
    // function call
    cout << hammingDist(str1, str2);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

C

// C program to find hamming distance b/w two string
#include <stdio.h>
 
// function to calculate Hamming distance
int hammingDist(char* str1, char* str2)
{
    int i = 0, count = 0;
    while (str1[i] != '\0') {
        if (str1[i] != str2[i])
            count++;
        i++;
    }
    return count;
}
 
// driver code
int main()
{
    char str1[] = "geekspractice";
    char str2[] = "nerdspractise";
    // function call
    printf("%d", hammingDist(str1, str2));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

Java

// Java program to find hamming distance b/w two string
class GFG {
    // function to calculate Hamming distance
    static int hammingDist(String str1, String str2)
    {
        int i = 0, count = 0;
        while (i < str1.length()) {
            if (str1.charAt(i) != str2.charAt(i))
                count++;
            i++;
        }
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str1 = "geekspractice";
        String str2 = "nerdspractise";
        // function call
        System.out.println(hammingDist(str1, str2));
    }
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

Python3

# Python3 program to find
# hamming distance b/w two
# string
 
# Function to calculate
# Hamming distance
def hammingDist(str1, str2):
    i = 0
    count = 0
 
    while(i < len(str1)):
        if(str1[i] != str2[i]):
            count += 1
        i += 1
    return count
 
# Driver code 
str1 = "geekspractice"
str2 = "nerdspractise"
 
# function call
print(hammingDist(str1, str2))
 
# This code is contributed by avanitrachhadiya2155

C#

// C# program to find hamming
// distance b/w two string
using System;
 
class GFG {
     
// function to calculate
// Hamming distance
static int hammingDist(String str1,
                       String str2)
{
    int i = 0, count = 0;
    while (i < str1.Length)
    {
        if (str1[i] != str2[i])
            count++;
        i++;
    }
    return count;
}
 
// Driver code
public static void Main ()
{
    String str1 = "geekspractice";
    String str2 = "nerdspractise";
 
    // function call
    Console.Write(hammingDist(str1, str2));
}
}
 
// This code is contributed by nitin mittal

PHP

<?php
// PHP program to find hamming distance b/w
// two string
 
// function to calculate
// Hamming distance
function hammingDist($str1, $str2)
{
    $i = 0; $count = 0;
    while (isset($str1[$i]) != '')
    {
        if ($str1[$i] != $str2[$i])
            $count++;
        $i++;
    }
    return $count;
}
 
    // Driver Code
    $str1 = "geekspractice";
    $str2 = "nerdspractise";
 
    // function call
    echo hammingDist ($str1, $str2);
     
// This code is contributed by nitin mittal.
?>

Javascript

<script>
// JavaScript program to find hamming distance b/w
// two string
 
// function to calculate Hamming distance
function hammingDist(str1, str2)
{
    let i = 0, count = 0;
    while (i < str1.length)
    {
        if (str1[i] != str2[i])
            count++;
        i++;
    }
    return count;
}
 
// driver code
    let str1 = "geekspractice";
    let str2 = "nerdspractise";
 
    // function call
    document.write(hammingDist (str1, str2));
 
 
 
// This code is contributed by Manoj.
</script>
Producción

4

Complejidad temporal: O(n)

Nota: Para la distancia de Hamming de dos números binarios, simplemente podemos devolver un recuento de bits establecidos en XOR de dos números.

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *