題目描述：

給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。

我們可以對一個單詞進行如下三種操作：

• 插入一個字符
• 刪除一個字符
• 替換一個字符

編輯距離：是指兩個字符串之間，由一個轉成另一個所需的最少編輯操作次數。
問題：word1到word2的編輯距離
子問題：word1前i個字符到word2前j個字符的編輯距離
假如有兩個字符串"hat"和"wtct"
每個格子表示word1前i個字符到word2前j個字符的編輯距離

i表示插入操作，d表示刪除操作，r表示替換操作。

第一行w可以由空字符串“”插入一個w得到，操作一次；wh可以由“”插入w再插入h得到，插入兩次，依次得到“”到whct的操作次數。

第一列由h變?yōu)?ldquo;”可以對h進行一次刪除操作，由ha變?yōu)?ldquo;”可以先刪除h再刪除a，操作兩次；由hat變?yōu)?ldquo;”可以進行三次刪除操作依次刪除三個字母。

F(1, 1)表示由h變?yōu)閣的編輯距離：

由h到w，可以先在h前面插入一個w，變?yōu)閣h，再把h刪除，操作兩次，即用F(0, 2)的狀態(tài)下再加一次刪除操作。
還可以先把h刪除，再插入一個w，操作兩次，即用F(1, 0)的狀態(tài)再加一次插入操作。
還可以把h替換成w，操作一次，可以用F(0, 0)的狀態(tài)加一次替換操作表示。
這三種操作都能將h變?yōu)閣，而我們需要的是最少的操作次數，所以選擇替換。F(1,1) 就為1。

F(1, 2)表示h變?yōu)閣h的編輯距離:

由h到wh，可以先在h的前面進行兩次插入操作插入wh，再將原來的h刪除，即可以用F(0, 2)的狀態(tài)加一次刪除操作。
還可以把h先替換成w，然后再插入h，即F(1, 1)的狀態(tài)再加一次插入操作。
還可以再h的前面直接插入w，即F(0, 1)的狀態(tài)，由于字符h和wh的第二個字符相同，所以不需要再進行替換操作，用F(0, 1)的狀態(tài)就可以表示F(1, 2)。
在這三種操作中，刪除操作是2+1為3，插入操作為1+1為2，不需要替換用F(0, 1)表示為1,。所以F(1, 2)為1。

F(2, 1)表示ha變?yōu)閣的編輯距離:

由ha變?yōu)閣，可以先將h變?yōu)閣，再把a刪除，即用F(1, 1)的狀態(tài)再加一次刪除操作。
還可以將ha變?yōu)?quot;"，再插入w，即用F(2, 0)再加一次插入操作。
還可以將h刪除，將a替換成w，即用F(1, 0)的狀態(tài)加一次替換操作。
刪除要兩次，插入要三次，替換要兩次。
所以F(2, 1)為2。

F(2, 2)表示ha變?yōu)閣h的編輯距離:

由ha變?yōu)閣h，可以先將h變?yōu)閣h，再刪除a，即用F(1, 2)的狀態(tài)再加一次刪除操作。
還可以ha先變?yōu)閣，再插入h，即F(2, 1)的狀態(tài)再加一次插入操作。
還可以將h替換成w，再將a替換成h，即F(1, 1)的狀態(tài)再加一次替換操作。
在這一步想要進行刪除操作需要2次(F(1, 2) + 1), 進行插入操作需要
3次(F(2, 1 + 1)), 進行替換操作需要2次(F(1, 1) + 1)，所以F(2, 2)為2。

經過分析可以得出狀態(tài)轉移方程：
word2的每一個子串都可由word1的子串進行插入，刪除，替換這三種操作得到，我們需要的是操作次數最少的結果，即：
F(i, j) = min(插入，刪除，替換)
F(i, j) = min(F(i, j - 1) + 1, F(i - 1, j) + 1, F(i - 1, j - 1) + (w1[i] == w2[j] ? 0 : 1))
這里需要注意的是替換操作如果word1[i]和word2[j]相等就不需要進行替換了。

代碼：

class Solution {
public:
? ? int minDistance(string word1, string word2) {
? ? ? ? int row = word1.size() + 1;
? ? ? ? int col = word2.size() + 1;
? ? ? ? int dp[row][col];
? ? ? ? //把第一行和第一列初始化
? ? ? ? for(int j = 0; j < col; ++j)
? ? ? ? {
? ? ? ? ? ? dp[0][j] = j;
? ? ? ? }
? ? ? ? for(int i = 0; i < row; ++i)
? ? ? ? {
? ? ? ? ? ? dp[i][0] = i;
? ? ? ? }
? ? ? ? //依次算出上圖每個格子的狀態(tài)
? ? ? ? for(int i = 1; i < row; ++i)
? ? ? ? {
? ? ? ? ? ? for(int j = 1; j < col; ++j)
? ? ? ? ? ? {
? ? ? ? ? ? ?? ?//如果兩次字符相等，不需要替換操作
? ? ? ? ? ? ?? ?//就像上圖的由h-->wh
? ? ? ? ? ? ? ? if(word1[i - 1] == word2[j - 1])
? ? ? ? ? ? ? ? ? ? dp[i][j] = dp[i - 1][j - 1];
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[row - 1][col - 1];
? ? }
};

到此這篇關于C++編輯距離（動態(tài)規(guī)劃）的文章就介紹到這了,更多相關C++編輯距離（動態(tài)規(guī)劃）內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論