# Levenshtein distance
- Note Created: 2022-02-17 @ 14:35
---
## General idea
The **Levenshtein distance** is a string metric for measuring the difference between two sequences.
Informally, the Levenshtein distance between two words is the **minimum number of single-character edits (insertions, deletions or substitutions) required** to change one word into the other.
## Code
Python 3 code to calculate the Levenshtein distance
```python
def levenshtein(x, y):
"""
Calculate the levenshtein distance between two strings.
"""
n = len(x)
m = len(y)
A = [[i + j for j in range(m + 1)] for i in range(n + 1)]
for i in range(n):
for j in range(m):
A[i + 1][j + 1] = min(A[i][j + 1] + 1, # insert
A[i + 1][j] + 1, # delete
A[i][j] + int(x[i] != y[j])) # replace
return A[n][m]
```
---
#### Related
#metrics #string_metric
[[Hamming distance]]