參考資料：
算法實(shí)現(xiàn)：Levenshtein Distance, in Three Flavors
原理：wiki-Levenshtein distance

該距離是俄羅斯科學(xué)家Vladimir Levenshtein在1965年發(fā)明的草添，也叫做編輯距離（實(shí)際上編輯距離代表一大類(lèi)算法）努隙，距離代表著從s到t需要?jiǎng)h戏仓、插谐鼎、代替單個(gè)字符的最小步驟數(shù)毕源。
主要應(yīng)用：

• Spell checking 檢查拼寫(xiě)
• Speech recognition 語(yǔ)音識(shí)別
• DNA analysis DNA分析
• Plagiarism detection 檢測(cè)抄襲

主要原理（理解下面的公式）：
ai跟bj之間的變化差距可以有很多種方法，這里限定最后一個(gè)字符ai和bj最后一個(gè)變化√耄可以刪除其中一個(gè)邦马，然后交給下一次去變化贱鼻，這里包含了min里面的前兩個(gè)；可以變換最后一個(gè)相等滋将，交給下一次去變化邻悬，最后一個(gè)相等的情況下，這里也可以不變随闽。

自己實(shí)現(xiàn)的：

import my_common


@my_common.print_result_after
def levenshtein_distance(str1,str2):
    matrix_width = len(str1) + 1
    matrix_height = len(str2) + 1
    matrix = [[0] * matrix_width for i in range(matrix_height)]

    # 初始化
    for i in range(matrix_width):
        matrix[0][i] = i

    for j in range(matrix_height):
        matrix[j][0] = j

    for i in range(1, matrix_height):
        for j in range(1, matrix_width, ):
            if str1[j - 1] == str2[i - 1]:
                cost = 0
            else:
                cost = 1
            try:
                a = matrix[i - 1][j] + 1
                b = matrix[i][j - 1] + 1
                c = matrix[i - 1][j - 1] + cost

                matrix[i][j] = min(a, b, c)
            except Exception as e:
                print(e)
                print('{}-{}'.format(i, j))
    print(matrix)
    return matrix[-1][-1]


# 遞歸版本
@my_common.print_result_after
def levenshtein_distance2(str1,str2):
    width = len(str1) + 1
    height = len(str2) + 1
    mat = [[-1]*width for _ in range(height)]

    def levenshtein_distance2_1(i, j):
        # 這個(gè)是為了遞歸的時(shí)候避免重復(fù)計(jì)算
        if mat[i][j] != -1:
            return mat[i][j]

        if i == 0:
            mat[i][j] = j
        elif j == 0:
            mat[i][j] = i
        else:
            if str2[i-1] == str1[j-1]:
                cost = 0
            else:
                cost = 1

            mat[i][j] = min(levenshtein_distance2_1(i-1,j)+1, levenshtein_distance2_1(i,j-1) + 1,
                            levenshtein_distance2_1(i - 1, j - 1) + cost)

        return mat[i][j]

    levenshtein_distance2_1(height-1,width-1)
    print(mat)
    return mat[-1][-1]


def main():
    str1 = 'hello'
    str2 = 'ello'
    # [[0, 1, 2, 3, 4, 5], [1, 1, 1, 2, 3, 4], [2, 2, 2, 1, 2, 3], [3, 3, 3, 2, 1, 2], [4, 4, 4, 3, 2, 1]]
    # 1
    levenshtein_distance2(str1,str2)


if __name__ == '__main__':
    main()