72. 编辑距离

Smile_slime_47
  2023-04-23 2023-04-23 Created  

原题地址：https://leetcode.cn/problems/edit-distance/

题解

参考官方题解

设dp[i][j]为word1子串[0,i]和word2子串[0,j]之间的编辑距离

  • 假设我们已经知道了dp[i][j-1]为a，即子串[0,i]在经过a步后得到子串[0,j-1]，理所当然地，[0,j-1]可以经过一步得到子串[0,j]
    • 此时编辑距离为a+1
  • 假设我们已经知道了dp[i-1][j]为b，即子串[0,j]在经过b步后得到子串[0,i-1]，理所当然地，[0,i-1]可以经过一步得到子串[0,i]
    • 此时编辑距离为b+1
  • 假设我们已经知道了dp[i-1][j-1]为c，即子串[0,i-1]在经过c步后得到子串[0,j-1]
    • 这时候我们扩展到dp[i][j]再看两个子串，实际上一个是[0,j-1][i]，另一个是[0,j-1]j
    • 如果word1.charAt(i)==word2.charAt(j)的话，实际上此时两个子串已经相等了
    • 此时编辑距离为c
    • 如果word1.charAt(i)!=word2.charAt(j)的话，则还需要最后一步操作：对两个子串中的任意一个子串的最后一个字符进行修改使其相等
    • 此时编辑距离为c+1

于是，我们可以得出dp公式：

考虑到几种边界情况：

  • 对于dp[i][0]/dp[0][j]，由一个空串得到子串[0,i]的编辑次数自然等于i，由一个空串得到子串[0,j]的编辑次数自然等于j
  • 当word1/word2中一者为空字符串时，直接返回另一者的length即可

时间复杂度：O(MN)

空间复杂度：O(MN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDistance(String word1, String word2) {
        if(word1.length()==0||word2.length()==0)return word1.length()+word2.length();
        int[][] dp=new int[word1.length()+1][word2.length()+1];
        for(int i=0;i<=word1.length();i++){
            dp[i][0]=i;
        }
        for(int i=0;i<=word2.length();i++){
            dp[0][i]=i;
        }

        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+(word1.charAt(i-1)==word2.charAt(j-1)?0:1));
            }
        }
        return dp[word1.length()][word2.length()];
    }
}
Comments
On this page
72. 编辑距离
  1. 题解