题解 | #计算字符串的编辑距离#

package main

import (
    "fmt"
)

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func calculateEditDistance(s1 string, s2 string) int {
    len1, len2 := len(s1), len(s2)
    // dp[i][j]: 表示 s1[:i] 和 s2[:j] 的编辑距离，则 dp[len1][len2] 即为所求
    dp := make([][]int, len1+1)
    for i:=0; i<len(dp); i++ {
        dp[i] = make([]int, len2+1)
    }

    // dp 初始化
    for i:=0; i<=len1; i++ {
        dp[i][0] = i
    }
    for j:=0; j<=len2; j++ {
        dp[0][j] = j
    }

    // 动态转移方程
    for i:=1; i<=len1; i++ {
        for j:=1; j<=len2; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                // 删除 s1 下标为 i-1 的元素
                // 删除 s2 下标为 j-1 的元素
                // 修改 s2 下标为 j-1 的元素
                dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
            }
        }
    }

    return dp[len1][len2]
}

func main() {
    var s1 string
    var s2 string

    fmt.Scan(&s1, &s2)

    fmt.Println(calculateEditDistance(s1, s2))
}

// 本题输入为两行字符串，所以采用：fmt.Scan(&s1, &s2)