题解 | #编辑距离(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str1 string字符串 
 * @param str2 string字符串 
 * @return int整型
*/
func editDistance( str1 string ,  str2 string ) int {
    n := len(str1)
    m := len(str2)
    memo := make([][]int, n)
    for i := 0; i < n; i++{
        memo[i] = make([]int, m)
        for j := 0; j < m; j++ {
            memo[i][j] = -1
        }
    }
    var dp func(int, int) int 
    dp = func (i, j int) int {
        if i == -1 {
            return j + 1
        }
        if j == -1 {
            return i + 1
        }
        if memo[i][j] != -1 {
            return memo[i][j]
        }
        if str1[i] == str2[j] {
            memo[i][j] = dp(i-1, j-1)
        }else {
            memo[i][j] = Min(dp(i, j-1)+1, dp(i-1, j)+1, dp(i-1, j-1)+1)
        }
        return memo[i][j]
    }
    return dp(n-1, m-1)
}
func Min(a, b, c int) int {
    if a < b || a < c {
        return a
    }else if b < a || b < c {
        return b
    }else {
        return c
    }
    
}