题解 | 编辑距离(一) 改正解题官思路

解题官的解法思路很好，但是如果两个字符串长度不一，但是最后一位字符相同的情况下，输出的结果错误。

如果两个字符串长度不同，可以考虑直接省略不同长度的字符串比较，直接比较相同长度下的字符，然后加上长度差（增加或删减）。

Python 优化后的代码如下，

class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        n = min(len(str1),len(str2)) # 以二者最短长度为n
        d = abs(len(str1)-len(str2)) # 计算二者的差值

        dp = [[0] * (n+1) for i in range(n+1)]

        for i in range(1, n+1): 
            dp[i][0] = dp[i - 1][0] + 1
            dp[0][i] = dp[0][i - 1] + 1

        for i in range(1, n+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 - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 
        return dp[n][n] + d