编辑距离
题目链接: https://leetcode.cn/problems/edit-distance/
解题思路:
设定二维数组dp[i][j],表示word1[i]转变到word2[j]需要的最少步数
word1[i]==word2[j] dp[i][j]=dp[i-1][j-1]
word1[i]!=word2[j] dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
dp[i-1][j-1]表示替换,dp[i-1][j]表示删除,dp[i]j-1]表示插入
dp[0][j]需要特殊处理,代表word1是"",变成word2的最少步骤,插入步骤,插入word2长度
dp[i][0]需要特殊处理,代表把word1从原字符串变成word2为空的最少步骤,删除步骤,删除word1长度
复杂度分析
时间复杂度: 时间复杂度是 ,其中 是字符串
word1
的长度, 是字符串word2
的长度空间复杂度: 空间复杂度是 ,我们需要一个l1*l2二维数组存储每个位置的状态。
最后更新于