没有输出的输入是不完整的

0%

leetcode-72-EditDistance

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

编辑距离是一个非常经典的动态规划的题目，之前搞懂过，但是总是会忘，所以又搞了一遍，顺便做个笔记。

题目描述

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

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

题目解读

就是求两个字符串的最小编辑距离，也就是计算word1最少可以经过多少次变化(插入，删除，替换)可以变成word2。

解题思路

动态规划的具体思路

  1. dp[i][j]表示word1的[0,i)变成word2的[0,j)位需要多少次变化。
  2. 对于第0行，dp[0][i] = i for 0<= i <= len2; (len2是word2的字符串长度)
  3. 对于第0列，dp[i][0] = i for 0=< i <= len1; (len1是word1的字符串长度)
  4. 如果最后一位相同，则arr[i][j] = arr[i-1][j-1]
  5. 若是判断的最后一位不同，则arr[i][j] = min(arr[i-1][j]+1, arr[i][j-1]+1 ,arr[i-1][j-1]+1)
  6. 最后返回arr[len1][len2]

细节剖析

这里解释一下第4步，也是看了好久才明白的。

下面以word1=“abb”,word2="ac"为例。

  1. 首先明确一下问题：我们现在要求的是abb需要多少步会变到ac，而假设我们已经知道了ab变ac，abb变a，ab变a三种情况，我们只需要现在的情况变到之前已知的情况就解决了。
  2. 假设abb->ac是从ab->ac变过来的，那么我们只要将abb去掉最后一个b就可以，剩下的就是要考虑ab如何变成ac了。也就是arr[i][j]=arr[i-1][j]+1;
  3. 假设abb->ac是从abb->a变过来的，那么我们只要在abb后面插入一个c就可以实现最后一位的匹配，剩下的就是考虑abb如何变成a了。也就是arr[i][j] = arr[i][j-1]+1;
  4. 假设abb->ac是从ab->a变过来的，那么我们只要将abb的最后一位变成c，剩下的就是考虑如何将ab变成a了。也就是arr[i][j]=arr[i-1][j-1]+1;
  5. 最后我们选一个从三种方式中修改次数最小的一个就可以了

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        
        int arr[len1+1][len2+1];
        memset(arr,0,sizeof arr);
        
        for(int i = 0; i <= len1; i++){
            arr[i][0] = i;
        }
        
        for(int i = 0; i <= len2; i++){
            arr[0][i] = i;
        }      
         for(int i = 1; i <= len1; i++){
             for(int j = 1;j <= len2; j++){
                 if(word1[i-1]==word2[j-1]){
                     arr[i][j] = arr[i-1][j-1];
                 }else{
                     arr[i][j] = min(min(arr[i-1][j],arr[i][j-1]),arr[i-1][j-1])+1;
                 }
             }
         }
        // for(int i = 0; i <= len1; i++){
        //      for(int j = 0;j <= len2; j++){
        //         cout<<arr[i][j]<<'\t';         
        //      }
        //     cout<<endl;
        // }
        
        return arr[len1][len2];
    }
};