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

秒懂【编辑距离】！动态规划一步步拆解。

1.思路

当str1[i-1]==str[j-1] 时，不用编辑，因此dp[i-1][j-1]。

当str1[i-1] != str[j-1] 时，需要编辑（删除、增加、或者修改选其中一个最小的值），因此dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str1 string字符串
# @param str2 string字符串
# @return int整型
#
class Solution:
    def editDistance(self, str1: str, str2: str) -> int:
        # write code here
        m = len(str1)
        n = len(str2)
        # 1. 定义状态.   dp[i][j]：字符串str1[0:i - 1] 与str2[0:j - 1] 的最少操作数
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        # 2. 初始化边界条件： dp[i][0] = i str1增加或删除i个元素会变成str2（str2为空）; dp[0][j] = j str2增加或删除j个元素会变成str1（str1为空）
        # 2.1 初始化第0行
        for j in range(n + 1):
            dp[0][j] = j
        # 2.2 初始化边界第0列
        for i in range(m + 1):
            dp[i][0] = i
        # 3.确定递推公式：
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]  # 若是字符相同，此处不用编辑,直接等于前一个的距离
                else:
                    # 删、增、修改中获取最小再加上1（删、增、修改对应于1次编辑）
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        # 4. 输出结果
        return dp[m][n]

2.2 Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str1 string字符串
     * @param str2 string字符串
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        int m = str1.length();
        int n = str2.length();
        // 1.定义状态.   dp[i][j]：字符串str1[0:i-1]与str2[0:j-1]的最少操作数
        int[][] dp = new int[m + 1][n + 1];
        // 2.初始化边界条件：dp[i][0] = i str1增加或删除i个元素会变成str2（str2为空）; dp[0][j] = j str2增加或删除j个元素会变成str1（str1为空）
        // 2.1初始化第0行
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        // 2.2初始化边界第0列
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        // 3.确定递推公式：
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    //若是字符相同，此处不用编辑,直接等于前一个的距离
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //删、增、修改中获取最小再加上1（删、增、修改对应于1次编辑）
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                }
            }
        }
        //4.输出结果
        return dp[m][n];
    }


    private int min(int a, int b, int c) {
        int res;
        if (a <= b && a <= c) {
            res = a;
        } else if (b <= a && b <= c) {
            res = b;
        } else {
            res = c;
        }
        return res;
    }
}

2.3 Go代码

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str1 string字符串
 * @param str2 string字符串
 * @return int整型
 */
func editDistance(str1 string, str2 string) int {
	// write code here
	m := len(str1)
	n := len(str2)
	// 1.定义状态.	   dp[i][j]：字符串str1[0:i-1]与str2[0:j-1]的最少操作数
	dp := newArray(m+1, n+1)
	// 2.初始化边界条件：dp[i][0] = i str1增加或删除i个元素会变成str2（str2为空）; dp[0][j] = j str2增加或删除j个元素会变成str1（str1为空）
	// 2.1初始化第0行
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	// 2.2初始化边界第0列
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	// 3.确定递推公式：
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if str1[i-1] == str2[j-1] {
				dp[i][j] = dp[i-1][j-1] //若是字符相同，此处不用编辑,直接等于前一个的距离
			} else {
				//删、增、修改中获取最小再加上1（删、增、修改对应于1次编辑）
				dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
			}
		}
	}
	//4.输出结果
	return dp[m][n]
}

// 创建一个 m行n列的矩阵（二维数组）
func newArray(m int, n int) [][]int {
	arr := make([][]int, m)
	for i := 0; i < m; i++ {
		arr[i] = make([]int, n)
	}
	return arr
}
func min(a, b, c int) int {
	var res int
	if a <= b && a <= c {
		res = a
	} else if b <= a && b <= c {
		res = b
	} else {
		res = c
	}
	return res
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构