Edit Distance(動态規劃)

Edit Distance

題目

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:

Insert a character

Delete a character

Replace a character

Example 1:

Input: word1 = “horse”, word2 = “ros”

Output: 3

Explanation:

horse -> rorse (replace ‘h’ with ‘r’)

rorse -> rose (remove ‘r’)

rose -> ros (remove ‘e’)

Example 2:

Input: word1 = “intention”, word2 = “execution”

Output: 5

Explanation:

intention -> inention (remove ‘t’)

inention -> enention (replace ‘i’ with ‘e’)

enention -> exention (replace ‘n’ with ‘x’)

exention -> exection (replace ‘n’ with ‘c’)

exection -> execution (insert ‘u’)

分析

用動态規劃的思想去解決這個問題，那麼意味着我們需要尋找這兩個字元串的子問題的解，那麼這個子問題怎麼解決呢？

我們采用一個二維數組來表示count[i][j]表示字元串長為i和字元串長為j的字元的編輯距離，對于子問題，我們可以采用将i和j逐漸縮小的政策，那麼最終問題可以看作解決count[i][j]，而每個字元串與空串的編輯距離是明顯的，及count[0][j]和count[i][0]是明顯知道的。

那麼對于子問題可以有一下三種情況

最後可以知道狀态轉移方程為：

其中diff(i,j)是指當串1和串2的下标i和下标j對應的字元相等的時候為0，否則需要一步編輯距離，則為1.

源碼

class Solution {
public:
    int minDistance(string word1, string word2) {
        int size1 = word1.size();
        int size2 = word2.size();
        vector<vector<int>> count(size1+1, vector<int>(size2+1, 0));
        for(int i = 0; i <= size1; i++) {
        	count[i][0] = i;
        }
        for(int i = 0; i <= size2; i++) {
        	count[0][i] = i;
        }

        for(int i = 1; i <= size1; i++) {
        	for(int j = 1; j <= size2; j++) {
        		int tag = 0;
        		if(word1[i-1] != word2[j-1]) {
        			tag = 1;
        		}
        		count[i][j] = min(count[i-1][j]+1, count[i][j-1]+1);
        		count[i][j] = min(count[i][j], tag+count[i-1][j-1]);
        	}
        }
        return count[size1][size2];
    }
};
           

覺得部落客寫的好

更多技術部落格：https://vilin.club/