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

编辑距离(一)，动态规划，空间O(min(m,n)

尾部元素str[i]和str[j]相等，不用编辑，编辑距离就是str1[:i]到str2[:j]的编辑距离。
尾部元素str[i]和str[j]不等：修改，对应的编辑距离是str1[:i]到str2[:j]的编辑距离+1。
尾部元素str[i]和str[j]不等：删除，对应的编辑距离是str1[:i]到str2[:j+1]的编辑距离+1。
尾部元素str[i]和str[j]不等：添加，对应的编辑距离是str1[:i+1]到str2[:j]的编辑距离+1。

class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        if len(str1) < len(str2):     # str2取小者
            str1, str2 = str2, str1
        m, n = len(str1), len(str2)
        dp = [j for j in range(n+1)]
        for i in range(m):
            dp[0] = i                   # 空-i个字符的编辑距离为i
            top_left = dp[0]                
            for j in range(n):
                if str2[j] == str1[i]:
                    tmp = dp[j+1]       # 当前的上方，等于下一个的左上方
                    dp[j+1] = top_left
                    top_left = tmp
                else:
                    tmp = dp[j+1]
                    dp[j+1] = min(dp[j+1], dp[j], top_left)+1
                    top_left = tmp
        return dp[-1]