In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences.
The symbols may be letters, bits, or decimal digits, among other possibilities. For example, the Hamming distance between:
- “karolin” and “kathrin” is 3.
- “karolin” and “kerstin” is 3.
- “kathrin” and “kerstin” is 4.
- 1011101 and 1001001 is 2.
- 2173896 and 2233796 is 3.
Given two words or numbers, find out the hamming distance between them.
数据结构和算法：初级练习题 #17 – 汉明距离
在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
- 对于固定的长度n，汉明距离是该长度字符向量空间上的度量，很显然它满足非负、唯一及对称性，并且可以很容易地通过完全归纳法证明它满足三角不等式。
- 两个字a与b之间的汉明距离也可以看作是特定运算−的a−b的汉明重量。
- 对于二进制字符串a与b来说，它等于a 异或b以后所得二进制字符串中“1”的个数。另外二进制字符串的汉明距离也等于n维超正方体两个顶点之间的曼哈顿距离，其中n是两个字串的长度。
汉明距离是以理查德·卫斯里·汉明的名字命名的，汉明在误差检测与校正码的基础性论文中首次引入这个概念。在通信中累计定长二进制字中发生翻转的错误数据位，所以它也被称为信号距离。
给定两个字符串或者两个数字，计算它们之间的汉明距离。下面是一些样例：
- “karolin” and “kathrin” is 3.
- “karolin” and “kerstin” is 3.
- “kathrin” and “kerstin” is 4.
- 1011101 and 1001001 is 2.
- 2173896 and 2233796 is 3.
Python Solution
