72. 编辑距离（动态规划）

题目

题解

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 定义状态：dp[i][j]表示将word1[0:i]转换成word2[0:j]所使用的最少操作数
        dp = [[0 for j in range(len(word2)+1)] for i in range(len(word1)+1)]

        # badcase: dp[0][j] = j, dp[i][0] = i
        for i in range(1, len(word1)+1):
            dp[i][0] = i
        for j in range(1, len(word2)+1):
            dp[0][j] = j

        # 状态转移
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                # skip
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # min(增加，删除，替换)
                    # 注意，替换也要加1个动作
                    dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1)

        return dp[len(word1)][len(word2)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23