Levenshein distance，中文名為最小編輯距離，其目的是找出兩個字符串之間需要改動多少個字符後變成一致。該算法使用了動態規劃的算法策略，該問題具備最優子結構，最小編輯距離包含子最小編輯距離，有下列的公式。
其中d[i-1,j]+1代表字符串s2插入一個字母，d[i,j-1]+1代表字符串s1刪除一個字母，然後當xi=yj時，不需要代價，所以和上一步d[i-1,j-1]代價相同，否則+1，接著d[i,j]是以上三者中最小的一項。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+y+O3qMq1z9ajqFB5dGhvbqOpo7o8L3A+CjxwPrzZyejBvbj219a3+7Sut9ax8M6qczGjrHMyo6zG5LOktsi31rHwzqpto6xuo6zK18/IyerH69K7uPajqG0mIzQzOzGjqSqjqG4mIzQzOzGjqbTz0KG1xL7Y1fOjrMi7uvO9q7Xa0rvQ0LrNtdrSu8HQs/XKvLuvo6xkW2ksMF09aaOsZFswLGpdPWqjrL3T18W+zbC01dW5q8q9x/Oz9r7Y1fPW0Mbky/vUqsvYo6y94cr4uvOjrMG9uPbX1rf7tK7WrrzktcSx4LytvuDA677NysdkW24sbV21xCYjMjA1NDA7o6y0+sLryOfPwqO6PC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">#!/usr/bin/env python
# -*- coding: utf-8 -*-
__author__ = 'xanxus'
s1, s2 = raw_input('String 1:'), raw_input('String 2:')
m, n = len(s1), len(s2)
colsize, matrix = m + 1, []
for i in range((m + 1) * (n + 1)):
matrix.append(0)
for i in range(colsize):
matrix[i] = i
for i in range(n + 1):
matrix[i * colsize] = i
for i in range(n + 1)[1:n + 1]:
for j in range(m + 1)[1:m + 1]:
cost = 0
if s1[j - 1] == s2[i - 1]:
cost = 0
else:
cost = 1
minValue = matrix[(i - 1) * colsize + j] + 1
if minValue > matrix[i * colsize + j - 1] + 1:
minValue = matrix[i * colsize + j - 1] + 1
if minValue > matrix[(i - 1) * colsize + j - 1] + cost:
minValue = matrix[(i - 1) * colsize + j - 1] + cost
matrix[i * colsize + j] = minValue
print matrix[n * colsize + m]
