LeetCode 72. Edit Distance题目解析-wowAC

Description

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:

a) Insert a character
b) Delete a character
c) Replace a character

题目复述

给定两个单词word1和word2,找出最小的步数使得word1转化为word2。

有下列三种操作(操作都针对word1,word2不动):

a) 插入一个字符

b) 删除一个字符

c) 替换一个字符

题目解析

很好的一道dp题目,在这里我们下标从1开始,定义dp[i][j]表示word1[0 – i]和word2[0-j]匹配所操作的步数。很显然边界条件为:

dp[0][j] = j(空word1插入j个字符), dp[i][0] = i(word1删除i个字符)。

dp[i][j] = min{

                            dp[i-1][j];     //对应的操作为删除word1[i]

                            dp[i][j-1];     //对应的操作为给word1后插入word2[j]

                            dp[i-1][j-1]; if word[i] == word[j]

                            dp[i-1][j-1] + 1; if word[i] != word[j],对应将word1[i]替换为word2[j]

            }

以第一个单词"INTENTION"和第二个单词"EXECUTION"为例,看下面的图,图中替换操作花费是2, 不过并不影响我们的理解。

上面是初始条件图,下面是整个dp矩阵完成的图。

参考资料:戳这儿

class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[900][900];
        dp[0][0] = 0;
        //边界条件
        for(int i=1; i<=word1.size(); i++) dp[i][0] = i;
        for(int j=1; j<=word2.size(); j++) dp[0][j] = j;
        
        for(int i=1; i<=word1.size(); i++)
        for(int j=1; j<=word2.size(); j++) {
            int res = 0x3f3f3f3f;
            res = min(res, dp[i-1][j]+1);   //删除i
            res = min(res, dp[i][j-1]+1);   //增加word2[j]
            if(word1[i-1] == word2[j-1])
                res = min(res, dp[i-1][j-1]); //都一样不需要操作
            else
                res = min(res, dp[i-1][j-1]+1); //将word1[i-1]改为word2[j-1]
            dp[i][j] = res;
        }
        return dp[word1.size()][word2.size()];
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注