Edit Distance

Description

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:

• Insert a character
• Delete a character
• Replace a character

Example
Given word1 = "mart" and word2 = "karma", return 3.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:    
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    int minDistance(string word1, string word2) {
        // write your code here
        // if (word1.empty()) {
        //     return word2.size();
        // }
        int w1 = word1.size();
        int w2 = word2.size();
        vector<vector<int>> dp(w1+1, vector<int>(w2+1, 0));
        //dp[0][0] =0;
        for (int i = 0; i <= w1; ++i) {
            for (int j = 0; j <= w2; ++j) {
                if (i == 0) {
                    // if word1 is empty, we need insert word2.size()
                    dp[i][j] = j;
                } else if (j == 0) {
                    // if word2 is empty, we need insert word1.size()
                    dp[i][j] =i;
                } else {
                    // whether the current char is the same, same->keep result
                    //         not same, +1 for replace
                    // whether the current char is missing in word1 or word2
                    //         if so, +1 for delete or insert
                    // Finally, find the minimum operation
                    dp[i][j] = min(dp[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0: 1),
                min(dp[i-1][j], dp[i][j-1])+1);
                }
            }
        }
        return dp[w1][w2];
    }
};

Similar problems

Longest Common Subsequence

Tags

x