A?=?"kitten"
B?=?"sitting"

編輯距離?=?3
解釋?zhuān)?
kitten?→?sitten（k?→?s）?→?sittin（e?→?i）→?sitting（插入?g）

dp[i][j]?=?min(
????dp[i-1][j]?+?1,??????????//?刪除
????dp[i][j-1]?+?1,??????????//?插入
????dp[i-1][j-1]?+?cost??????//?替換/匹配
)

package?main

import?(
????"fmt"
????"math"
)

func?MinDistance(a,?b?string)?int?{
????m,?n?:=?len(a),?len(b)
????dp?:=?make([][]int,?m+1)

????//?初始化二維數(shù)組
????for?i?:=?range?dp?{
????????dp[i]?=?make([]int,?n+1)
????}

????//?初始化第一列和第一行
????for?i?:=?0;?i?<=?m;?i++?{
????????dp[i][0]?=?i
????}
????for?j?:=?0;?j?<=?n;?j++?{
????????dp[0][j]?=?j
????}

????//?狀態(tài)轉(zhuǎn)移
????for?i?:=?1;?i?<=?m;?i++?{
????????for?j?:=?1;?j?<=?n;?j++?{
????????????cost?:=?0
????????????if?a[i-1]?!=?b[j-1]?{
????????????????cost?=?1
????????????}
????????????dp[i][j]?=?min(
????????????????dp[i-1][j]+1,???//?刪除
????????????????dp[i][j-1]+1,???//?插入
????????????????dp[i-1][j-1]+cost,?//?替換/匹配
????????????)
????????}
????}

????return?dp[m][n]
}

func?min(a,?b,?c?int)?int?{
????return?int(math.Min(float64(a),?math.Min(float64(b),?float64(c))))
}

func?main()?{
????a?:=?"kitten"
????b?:=?"sitting"
????fmt.Printf("編輯距離?between?'%s'?and?'%s'?is:?%d\n",?a,?b,?MinDistance(a,?b))
}

輸入：
a?=?"kitten"
b?=?"sitting"

輸出：
編輯距離?between?'kitten'?and?'sitting'?is:?3

func?MinDistanceOptimized(a,?b?string)?int?{
????m,?n?:=?len(a),?len(b)
????prev?:=?make([]int,?n+1)
????curr?:=?make([]int,?n+1)

????//?初始化第一行
????for?j?:=?0;?j?<=?n;?j++?{
????????prev[j]?=?j
????}

????for?i?:=?1;?i?<=?m;?i++?{
????????curr[0]?=?i
????????for?j?:=?1;?j?<=?n;?j++?{
????????????cost?:=?0
????????????if?a[i-1]?!=?b[j-1]?{
????????????????cost?=?1
????????????}
????????????curr[j]?=?min(
????????????????curr[j-1]+1,??????//?插入
????????????????prev[j]+1,????????//?刪除
????????????????prev[j-1]+cost,???//?替換
????????????)
????????}
????????prev,?curr?=?curr,?prev
????}

????return?prev[n]
}

similarity?:=?1?-?float64(distance)?/?float64(max(len(a),?len(b)))