File size: 1,021 Bytes
9438a57 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
def levenshtein(source, target):
if source == '' or target == '':
return len(source) or len(target)
elif source[0] == target[0]:
return levenshtein(source[1:], target[1:])
else:
return 1 + min(
levenshtein(source, target[1:]),
levenshtein(source[1:], target[1:]),
levenshtein(source[1:], target)
)
"""
Levenshtein Distance
Calculates the Levenshtein distance between two strings. The Levenshtein distance is defined as the minimum amount of single-character edits (either removing a character, adding a character, or changing a character) necessary to transform a source string into a target string.
Input:
source: The string you begin with.
target: The string to transform into.
Output:
The Levenshtein distance between the source and target.
Example:
electron can be transformed into neutron by removing the e, turning the l into n, and turning the c into u.
>>> levenshtein(electron, neutron)
3
"""
|