python实现leetcode之72. 编辑距离

解题思路

经典的动态规划问题
最优子结构对应三种操作

72. 编辑距离

代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        columns = len(word1) + 1
        rows = len(word2) + 1
        matrix = [[0 for _ in range(columns)][:] for _ in range(rows)]
        for row in range(rows):
            for col in range(columns):
                if row == 0: matrix[row][col] = col
                elif col == 0: matrix[row][col] = row
                else:
                    if word1[col-1] == word2[row-1]:
                        matrix[row][col] = matrix[row-1][col-1]
                    else:
                        matrix[row][col] = min(matrix[row-1][col-1], # 替换
                                           matrix[row-1][col],  # word1减一个字符
                                           matrix[row][col-1]   # word2减一个字符
                                           ) + 1
        return matrix[-1][-1]