[LeetCode]72. Edit Distance

正午 2020-01-08 PM 7℃ 0条

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

虽然题目出现的地方比较多了,看到英文的描述有清晰了几分,把 word1 转换成 word2 的最少操作次数,所有的操作都是针对word1 的确定这个才比较好理解下面每种情况对应的是替换还是删除和增加

dpi 表示 word1[:i] 和 word2[:j] 直接的最小编辑距离,

  1. word1[i] == word2[j]
    dpi = dpi-1
  2. word1[i] != word[j]
    dpi = min(dpi-1, dpi, dpi-1) + 1

dpi-1 + 1 对应删除操作,dpi 对应insert 操作 dpi-1 +1 对应替换

class Solution {
public:
    int minDistance(string word1, string word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        vector<vector<int>> dp(l1+1, vector<int>(l2+1,0));
        for(int i=0; i< l1+1; i++){
            dp[i][0] = i;
        }
        for(int j=0; j< l2+1; j++){
            dp[0][j] = j;
        }
        for(int i=0; i< l1; i++){
            for(int j=0; j< l2; j++){
                if (word1[i]==word2[j]){
                   dp[i+1][j+1] = dp[i][j];
                }else{
                    dp[i+1][j+1] = min(min(dp[i][j],dp[i+1][j]),dp[i][j+1]) + 1;
                }
            }
        }
        return dp[l1][l2];
    }
};
标签: LeetCode

非特殊说明,本博所有文章均为博主原创。

评论