golang题解 | 编辑距离(二)

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * min edit cost
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @param ic int整型 insert cost
 * @param dc int整型 delete cost
 * @param rc int整型 replace cost
 * @return int整型
*/
func minEditCost(s string, t string, ic int, dc int, rc int) int {
    n := len(s)
    m := len(t)

    mem := make([][]int, n)
    for i := range mem {
        mem[i] = make([]int, m)
        for j := range mem[i] {
            mem[i][j] = -1
        }
    }

    var dfs func(int, int) int
    dfs = func(i, j int) (ans int) {
        if i < 0 {
            // 下标为 0~j 的字符串长度为 j+1
            return (j + 1) * ic
        }
 
        if j < 0 {
		  // 下标为 0~i 的字符串长度为 i+1
            return (i + 1) * dc
        }
 
        p := &mem[i][j]
        if *p != -1 {
            return *p
        }
 
        defer func(){
            *p = ans
        }()
 
        if s[i] == t[j] {
            return dfs(i - 1, j - 1)
        }
 
        return min(dfs(i, j - 1) + ic, min(dfs(i - 1, j) + dc, dfs(i - 1, j - 1) + rc))
    }
 
    return dfs(n - 1, m - 1)
}

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