72. Edit Distance

Description

Given two wordsword1andword2, find the minimum number of steps required to convertword1toword2. (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

Discuss

Method

dp 匹配

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

        for(int i = 0; i <= word2.size(); ++i) {
            dp[0][i] = i;
        }

        for(int yLoop = 1; yLoop <= word1.size(); ++yLoop) {
            for(int xLoop = 1; xLoop <= word2.size(); ++xLoop) {
                /*
                dp[yLoop][xLoop] = min(dp[yLoop - 1][xLoop - 1], min(dp[yLoop][xLoop - 1], dp[yLoop - 1][xLoop]));
                if(word1[yLoop-1] != word2[xLoop-1]) {
                    ++dp[yLoop][xLoop];
                }
                */
                if(word1[yLoop-1] != word2[xLoop-1]) {
                    dp[yLoop][xLoop] = min(dp[yLoop - 1][xLoop - 1], min(dp[yLoop][xLoop - 1], dp[yLoop - 1][xLoop])) + 1;
                }
                else {
                    dp[yLoop][xLoop] = dp[yLoop - 1][xLoop - 1];
                }
            }
        }

        return dp[word1.size()][word2.size()];
    }
};