72 Edit Distance

题目

Edit Distance

题解

假设字符串word1由字符\(s_1s_2 ... s_m\)组成，word2由\(t_1t_2 ... t_n\)组成，让我们首先从距离答案只有一步之遥的末尾开始思考：如果\(s_m\)与\(t_n\)相同，那我们只需求解从\(s_1s_2 ... s_{m-1}\)到\(t_1t_2 ... t_{n-1}\)的最小编辑距离\(edit[m-1][n-1]\)即可；如果\(s_m\)与\(t_n\)不同，因为单次编辑只有替换、插入或删除一个字符这三种操作，所以只存在下面三种情况：

1. 在\(edit[m-1][n-1]\)的基础上替换\(s_m\)
2. 在\(edit[m][n-1]\)的基础上插入\(t_n\)
3. 在\(edit[m-1][n]\)的基础上删除\(s_m\)

注意到\(edit[m-1][n-1]\)、\(edit[m][n-1]\)和\(edit[m-1][n]\)都是\(edit[m][n]\)的子问题，这表示我们可以用较小的子问题的解，通过上面三个状态转移方程，构造出问题的解，只要再找出初始状态，我们就能运用动态规划的方法来求解这个问题了。不难看出，当word1或者word2为空时，\(edit[m][n]\)等于另一个字符串的长度。至此我们就找齐了使用动态规划算法的全部条件了。

代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        length1 = len(word1)
        length2 = len(word2)

        dynamic_programming = [[0] * (length2 + 1) for _ in range(length1 + 1)]
        for i in range(1, length1 + 1):
            dynamic_programming[i][0] = i
        for j in range(1, length2 + 1):
            dynamic_programming[0][j] = j

        for i in range(1, length1 + 1):
            for j in range(1, length2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dynamic_programming[i][j] = dynamic_programming[i - 1][j - 1]
                else:
                    dynamic_programming[i][j] = (
                        min(
                            dynamic_programming[i - 1][j - 1],
                            dynamic_programming[i - 1][j],
                            dynamic_programming[i][j - 1],
                        )
                        + 1
                    )

        return dynamic_programming[length1][length2]

拓展

• 此题中的Edit Distance实为计算机科学中的Levenshtein distance
• 观察下面这张edit表格，可以看出计算\(edit[i][j]\)只需要表格中的第\(i-1\)和\(i\)行，可以据此进行空间复杂度的优化

↓index→	0			j-1	j			n
0	0	1	.	j-1	j	.	.	n
	1
	.
i-1	i-1			\(edit[i-1,j-1]\)	\(edit[i-1,j]\)
i	i			\(edit[i,j-1]\)
	.
	.
m	m