Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Edit Distance

Leetcode algorithms 第 72 题:Edit Distance。

题目

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

解答

两个字符串的edit distance为把第一个字符串转化为第二个字符串所需要最少步数,每次可以插入、删除或替换一个字符。明显可以使用动态规划,令dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符的edit distance,则求dp[i][j]时,需要考虑word1[i-1]和word2[j-1]的关系:

  • 如果二者相等,则直接匹配了,dp[i][j] = dp[i-1][j-1]。
  • 否则,可以进行三种操作,增加字符等价于word2的长度减1,减少字符等价于word1的长度减1,替换字符等价于word1和word2长度均减1,即dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

据此可以直接得到动态规划的代码。初始化是一个字符串长度为0时,其edit distance为第二个字符串的长度。

具体代码如下:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[1000][1000]; //dp[i][j:word1的前i个字符和word2的前j个字符的edit distance
        
        int n1 = word1.size(), n2 = word2.size();
        for (int i = 0; i <= n1; i++) dp[i][0] = i; //初始化
        for (int i = 0; i <= n2; i++) dp[0][i] = i;
        
        for (int i = 1; i <= n1; i++)
            for (int j = 1; j <= n2; j++)
            {
                if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
            }
        
        return dp[n1][n2];
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论