leetcode Edit Distance

约定不等于承诺〃 2022-08-01 11:18 176阅读 0赞

# 题目 #

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

题目来源：[https://leetcode.com/problems/edit-distance/][https_leetcode.com_problems_edit-distance]

# 分析 #

动态规划。既然允许三种操作：插入、删除和替换，那么就三个操作都做然后选取一种最小的。dp\[i\]\[j\]表示word1前i个字符和word2前j个字符之间的最小距离，递推公式就是：

如果word1的第i个字符和word2的第j个字符相同；  
dp\[i\]\[j\] = dp\[i-1\]\[j-1\]  
否则  
dp\[i\]\[j\] = min(dp\[i-1\]\[j-1\]+1, dp\[i-1\]\[j\] + 1, dp\[i\]\[j-1\] + 1)

dp\[i-1\]\[j-1\]+1表示增加一次替换操作；  
dp\[i-1\]\[j\]+1表示word2执行insert操作或者word1执行delete操作；  
dp\[i\]\[j-1\]+1表示word1执行insert操作或者word2执行delete操作。

# 代码 #

class Solution {
    public:
        int minDistance(string word1, string word2) {
            int len1 = word1.length() + 1;
            int len2 = word2.length() + 1;
            vector<vector<int> > dp(len1, vector<int>(len2, 0));
            for(int i = 0; i < len1; i++){
                dp[i][0] = i;
            }
            for(int i = 0; i < len2; i++){
                dp[0][i] = i;
            }
    
            for(int i = 1; i < len1; i++){
                for(int j = 1; j < len2; j++){
                    if(word1.at(i-1) == word2.at(j-1))
                        dp[i][j] = dp[i-1][j-1];
                    else
                        dp[i][j] = min(dp[i-1][j-1]+1, min(dp[i-1][j] + 1, dp[i][j-1] + 1));
                }
            }
            return dp[len1-1][len2-1];
        }
    };

[https_leetcode.com_problems_edit-distance]: https://leetcode.com/problems/edit-distance/