Calculates Levenshtein-distance between strings

levenshtein.py

#!/bin/python
# https://en.wikipedia.org/wiki/Optimal_string_alignment
def distance(s, t):
    """Calculate Levenshtein distance between words s and t"""
    m, n = len(s), len(t)
    d = [[0 for j in range(n)] for i in range(m)]

    for i in range(1, m):
        d[i][0] = i

    for j in range(1, n):
        d[0][j] = j

    for j in range(1, n):
        for i in range(1, m):
            if s[i] == t[j]:
                d[i][j] = d[i-1][j-1]
            else:
                d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + 1)
    return d[m-1][n-1]

if __name__ == "__main__":
    # run a basic test
    import sys
    if len(sys.argv) == 3:
        print distance(sys.argv[1], sys.argv[2])
    else:
        assert distance("abc","ad") == 2
        assert distance("abc","ac") == 1
        assert distance("abc","ab") == 1
        assert distance("abc","abc") == 0