Levenshtein distance between two sequences

levenshtein.py

def _LevenshteinDistance(str1, i, len1, str2, j, len2, cache):
    key = (i, len1, j, len2)

    if key in cache:
        return cache[key]
    if len1 == 0:
        return len2
    if len2 == 0:
        return len1

    cost = 0
    if str1[i] != str2[j]:
        cost = 1

    dist = min(
        _LevenshteinDistance(str1, i+1, len1-1, str2, j,   len2,   cache) + 1,
        _LevenshteinDistance(str1, i,   len1,   str2, j+1, len2-1, cache) + 1,
        _LevenshteinDistance(str1, i+1, len1-1, str2, j+1, len2-1, cache) + cost)
    cache[key] = dist
    return dist

def LevenshteinDistance(str1, str2):
    return _LevenshteinDistance(str1, 0, len(str1), str2, 0, len(str2), {})