Edit Distance

Problem Statement

Given two input strings, word1 and word2, the task is to determine the minimum number of single-character operations required to transform word1 into word2. The permitted operations involve:

• Inserting a character into the string.
• Deleting a character from the string.
• Replacing one character in the string with another.

This problem can be visualized as finding the minimal path through a series of edits that converts the first string into the second string, where each operation counts as a single step along that path.

Examples

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')

Constraints

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

Approach and Intuition

To solve the problem of converting one string to another with the minimum operations, we can utilize Dynamic Programming (DP), where each subproblem builds upon solutions to smaller subproblems. The core idea revolves around creating a DP table where dp[i][j] represents the minimum number of operations required to convert the substring word1[0...i-1] to word2[0...j-1].

1. Initialization:

   • If word1 is an empty string, the number of operations to convert it to word2 is simply the length of word2 (all insert operations).
   • If word2 is an empty string, the number of operations to convert word1 to it is the length of word1 (all delete operations).

2. Recursive Case:

   • For two indices i and j, consider the characters word1[i-1] and word2[j-1]. If these characters are the same, the operations required to transform up to these indices is the same as transforming up to i-1 and j-1, hence dp[i][j] = dp[i-1][j-1].
   • If the characters differ, consider three possible operations:
     • Insert: Inserting the j-th character of word2 into word1 would mean working off the results already obtained for dp[i][j-1].
     • Delete: Deleting the i-th character from word1 would rely on results from dp[i-1][j].
     • Replace: Replacing i-th character of word1 with the j-th of word2 builds on dp[i-1][j-1].

3. Choose the Minimum:

   • After considering all possible operations, the value at dp[i][j] is the minimal value among the three evaluated possibilities (insert, delete, replace) plus one (the operation itself).

4. Completion:

   • The final answer, the minimal number of operations required to convert word1 to word2, is found in dp[length of word1][length of word2].

Example Walkthrough

• Example 1: Converting "horse" to "ros"

  • Starting from 'h' in "horse", replacing it with 'r' forms "rorse".
  • Removing the first 'r' in "rorse" forms "rose".
  • Removing 'e' in "rose" leads to "ros".
  • Total operations: 3

• Example 2: Converting "intention" to "execution"

  • Initial deletion, replacements and an insertion yield a minimal transformation sequence involving 5 operations, fully detailed in the problem examples.

This approach ensures we systematically evaluate the possible transformations from one string to another, leveraging prior calculations to minimize the overall number of operations, falling within the constraints given (string lengths up to 500).

Solutions

class Solution {
public:
    vector<vector<int>> distanceMemo;
    int minDistance(string str1, string str2) {
        int len1 = str1.size();
        int len2 = str2.size();
        if (len1 == 0) return len2;
        if (len2 == 0) return len1;
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 1; i <= len1; ++i) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= len2; ++j) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
            }
        }
        return dp[len1][len2];
    }
};