levenshtein_distance.py

#!/usr/bin/env python


def levenshtein_distance(a, b):
    '''
    Algorighm: Dynamic Programming, DP

    a: apple
    b: python
                          b (j)
       [0, 0, 0, 0, 0, 0, 0]       [0, 1, 2, 3, 4, 5, 6]
       [0, 0, 0, 0, 0, 0, 0]       [1, 1, 2, 3, 4, 5, 6]
       [0, 0, 0, 0, 0, 0, 0]  -->  [2, 1, 2, 3, 4, 5, 6]
       [0, 0, 0, 0, 0, 0, 0]       [3, 2, 2, 3, 4, 5, 6]
       [0, 0, 0, 0, 0, 0, 0]       [4, 3, 3, 3, 4, 5, 6]
     a [0, 0, 0, 0, 0, 0, 0]       [5, 4, 4, 4, 4, 5, 6]
    (i)
    '''
    m = [[0] * (len(b) + 1) for i in xrange(len(a) + 1)]

    for i in xrange(len(a) + 1):
        '''
        [0, 0, 0, 0, 0, 0, 0]
        [1, 0, 0, 0, 0, 0, 0]
        [2, 0, 0, 0, 0, 0, 0]
        [3, 0, 0, 0, 0, 0, 0]
        [4, 0, 0, 0, 0, 0, 0]
        [5, 0, 0, 0, 0, 0, 0]
        '''
        m[i][0] = i

    for j in xrange(len(b) + 1):
        '''
        [0, 1, 2, 3, 4, 5, 6]
        [1, 0, 0, 0, 0, 0, 0]
        [2, 0, 0, 0, 0, 0, 0]
        [3, 0, 0, 0, 0, 0, 0]
        [4, 0, 0, 0, 0, 0, 0]
        [5, 0, 0, 0, 0, 0, 0]
        '''
        m[0][j] = j

    for i in xrange(1, len(a) + 1):
        for j in xrange(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                x = 0
            else:
                x = 1
            m[i][j] = min(m[i - 1][j] + 1,
                          m[i][j - 1] + 1,
                          m[i - 1][j - 1] + x)
    return m[-1][-1]

# import sys
#
# s1 = sys.argv[1]
# s2 = sys.argv[2]
s1 = 'apple'
s2 = 'python'

print(levenshtein_distance(s1, s2))