AcWing 902. GoLang - Edit Distance - DP, 2D
原题链接
简单
作者:
idiotleon
,
2020-12-28 13:08:55
,
所有人可见
,
阅读 335
package main
import "fmt"
const N = 1000 + 7
func main(){
var n, m int
fmt.Scanf("%d", &n)
chs1 := make([]byte, N)
for idx := 0; idx <= n; idx++{
fmt.Scanf("%c", &chs1[idx])
}
fmt.Scanf("%d", &m)
chs2 := make([]byte, N)
for idx := 0; idx <= m; idx++{
fmt.Scanf("%c", &chs2[idx])
}
costs := make([][]int, n + 1)
for idx := range costs{
costs[idx] = make([]int, m + 1)
}
for idx := 0; idx <= n; idx++{
costs[idx][0] = idx
}
for idx := 0; idx <= m; idx++{
costs[0][idx] = idx
}
for idx1 := 0; idx1 < n; idx1++{
for idx2 := 0; idx2 < m; idx2++{
if chs1[idx1] == chs2[idx2] {
costs[idx1 + 1][idx2 + 1] = costs[idx1][idx2]
}else{
insertion := costs[idx1][idx2 + 1]
replacement := costs[idx1][idx2]
deletion := costs[idx1 + 1][idx2]
costs[idx1 + 1][idx2 + 1] = 1 + minOf(insertion, replacement, deletion)
}
}
}
fmt.Println(costs[n][m])
}
func minOf(vars ...int) int{
min := vars[0]
for _, val := range vars{
if val < min{
min = val
}
}
return min
}