题解 | #编辑距离#

// import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str1 string字符串 
 * @param str2 string字符串 
 * @return int整型
*/
func editDistance( str1 string ,  str2 string ) int {
    // write code here
    n1, n2 := len(str1), len(str2)
    dp := make([][]int, n1+1)  // dp[i][j] //以i-1为结尾的字符串str1，和以j-1位结尾的字符串str2，想要达到相等，所需要删除元素的最少次数。
    for i:=0;i<n1+1;i++{
        dp[i] = make([]int, n2+1)
    }
    for i:=0;i<=n1;i++{
        dp[i][0] = i
    }
    for j:=0;j<=n2;j++{
        dp[0][j] = j
    }
    
    for i:=1;i<=n1;i++{
        for j:=1;j<=n2;j++{
            if str1[i-1]==str2[j-1]{
                dp[i][j] = dp[i-1][j-1]
            }else{
                //min(替换，删除str1，删除str2)
                dp[i][j] = min(dp[i-1][j-1]+1, min(dp[i-1][j], dp[i][j-1])+1)
            }
        }
    }
    return dp[n1][n2]
}

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