問(wèn)題

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

例子

abc bad
3

分析

最優(yōu)化問(wèn)題 + 大問(wèn)題可以用小問(wèn)題來(lái)解決 => 動(dòng)態(tài)規(guī)劃

1. 狀態(tài)表
   dp[i][j] word1[0, i-1]轉(zhuǎn)化為word2[0, j-1]的最小步數(shù)

2. 初始狀態(tài)
   dp[0][0] = 0 空串=空串，不需要轉(zhuǎn)化；
   dp[i][0] = i, i >= 1 長(zhǎng)度為i的字符串轉(zhuǎn)化為空串，需要添加i個(gè)字符串；
   dp[0][j] = j, j >= 1 空串轉(zhuǎn)化為長(zhǎng)度為j的字符串，需要?jiǎng)h除i個(gè)字符串。

3. 狀態(tài)轉(zhuǎn)移方程
   dp[i][j] = dp[i - 1][j - 1], if word1[i - 1] == word2[j - 1]
   注：當(dāng)word1的第i個(gè)字符和word2的第j個(gè)字符相等時(shí)， word1[0, i-1]轉(zhuǎn)化為word2[0, j-1]的最小步數(shù)等于word1[0, i-2]轉(zhuǎn)化為word2[0, j-2]的最小步數(shù)
   dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1, if word1[i - 1] != word2[j - 1]
   注：當(dāng)word1的第i個(gè)字符和word2的第j個(gè)字符不相等時(shí)，word1可以先轉(zhuǎn)換、刪除第i個(gè)字符，或者在word2添加第j個(gè)字符，然后再進(jìn)一步轉(zhuǎn)化為word2。第一步都需要1次轉(zhuǎn)化，第二步分別需要dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]次轉(zhuǎn)化。取最小值即可。

要點(diǎn)

dp

時(shí)間復(fù)雜度

O(mn)

空間復(fù)雜度

O(mn)

代碼

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++)
            dp[i][0] = i;
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                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[m][n];
    }
};

空間復(fù)雜度為O(2n)的代碼

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(2, vector<int>(n + 1, 0));
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;

        int flag = 0;
        for (int i = 1; i <= m; i++) {
            dp[!flag][0] = i;
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) dp[!flag][j] = dp[flag][j - 1];
                else dp[!flag][j] = min(dp[flag][j - 1], min(dp[flag][j], dp[!flag][j - 1])) + 1;
            }
            flag = !flag;
        }
        return dp[flag][n];
    }
};

空間復(fù)雜度為O(n)的代碼

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<int> dp(n + 1, 0);
        for (int j = 1; j <= n; j++)
            dp[j] = j;
            
        for (int i = 1; i <= m; i++) {
            int pre = dp[0];
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (word1[i - 1] == word2[j - 1]) dp[j] = pre;
                else dp[j] = min(pre, min(dp[j], dp[j - 1])) + 1;
                pre = temp;
            }
        }
        return dp[n];
    }
};