HelloKenLee

Leetcode 72. Edit Distance 解题报告

Posted on By KenLee

题目信息

题目: 72. Edit Distance
难度: Hard
正确率: 31%
问题描述:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

问题分析

  该题的大意是说给出两个字符串,求出他们的编辑距离。编辑距离的定义为修改一个字符,添加一个字符,或者插入一个字符的花费为1,求总花费。

解题思路

  典型的动态规划问题,假设两个字符串为str1str2不妨定义dp[i][j]str1的前i个字符组成的子串和str2的前j个组成的子串的编辑距离
  则有状态转移如下:


   其含义为:

  • $ dp[i-1][j-1] + (str1[i-1]==str2[j-1]) $ : 是通过若干操作+最后一个replace操作得到的,即我们只需要把str1[i-1]替换成str2[j-1],如果这两个字符相等,则花费为0。
  • $ dp[i-1][j] + 1 $ : 是通过若干操作+最后一次操作得到的,最后一次操作为往str1[0..i-1]中添加str2[j-1]得到,操作花费为1。(或者理解为在str2[0..j-1]删除str[j-1]得到str1[0..i-1], 两者是等效的)。
  • $ dp[i][j-1] + 1 $ : 和上面一个意思,str1str2互换。

结果分析

  • 时间复杂度: $ O(N^2) $ , 分成 $ N^2 $个子问题, 解决每一个子问题的复杂度为 $ O(1) $
  • 空间复杂度: $ O(N^2) $, 可以优化为 $ O(N) $
  • 通过时间: 9 ms
  • 击败: 51.14%的提交

源代码

class Solution {
public:
    /*
        dp[i][j] 定义为 word1 的前i位变为 word2 的前j位需要的最小编辑距离;
        有:
        dp[i][i] = min(
            dp[i-1][j-1] + (word1[i] == word[j]),//通过replace得到
            dp[i-1][j] + 1,//通过往insert/delete得到
            dp[i][j-1] + 1,//通过往insert/delete得到
        )
    */
    int minDistance(string word1, string word2) {
        const int N = max(word1.size(), word2.size());
        vector<vector<int>> dp(N + 1, vector<int>(N + 1, 1));
        // init
        for(int i = 0; i <= N; ++i){
            dp[0][i] = i;
            dp[i][0] = i;
        }
        // calc
        for(int i = 1; i <= N; ++i){
            for(int j = 1; j <= N; ++j){
                dp[i][j] = dp[i-1][j-1] + (word1[i-1] != word2[j-1]);
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1);
            }
        }
        return dp[word1.size()][word2.size()];
    }
};