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

class Solution:  
    def editDistance(self, str1: str, str2: str) -> int:  
        m, n = len(str1), len(str2)  
        dp = [[0] * (n + 1) for _ in range(m + 1)]  
          
        # 初始化边界条件  
        for i in range(m + 1):  
            dp[i][0] = i  
        for j in range(n + 1):  
            dp[0][j] = j  
          
        # 填充dp数组  
        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:  
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1  
          
        return dp[m][n]