algoadvance

Leetcode 72. Edit Distance

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Clarifying Questions

Before we proceed, let’s clear out any ambiguities:

  1. Can the operations be performed in any sequence/order?
    • Yes, the operations can be performed in any order as needed.
  2. What is the length range for the input strings?
    • The input strings can have a length ranging from 0 to 500.
  3. Are there any constraints on the characters within the strings?
    • The input strings consist of lowercase English letters.

Strategy

To solve the problem, we can use Dynamic Programming (DP). We need to maintain a DP table where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2.

We can break down the problem into the following steps:

  1. If one of the strings is empty, the edit distance is the length of the other string (since all characters need to be either inserted or deleted).
  2. If the last characters of the substrings (prefixes) being compared are the same, the edit distance is the same as for the prefixes one character shorter.
  3. If the last characters are different, we consider all possibilities: insert, delete, and replace, and take the minimum result.

Code

Here is the C++ implementation of the solution:

#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
        int m = word1.size();
        int n = word2.size();
        
        // DP table with (m+1)x(n+1)
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
        
        // Initialize for the case when one of the strings is empty
        for(int i = 1; i <= m; i++) {
            dp[i][0] = i; // Deleting all characters in word1
        }
        for(int j = 1; j <= n; j++) {
            dp[0][j] = j; // Inserting all characters to form word2
        }
        
        // Fill the DP table
        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]; // No change needed
                } else {
                    dp[i][j] = std::min({dp[i-1][j] + 1,    // Delete
                                         dp[i][j-1] + 1,    // Insert
                                         dp[i-1][j-1] + 1}); // Replace
                }
            }
        }
        
        return dp[m][n];
    }
};

Time Complexity

The time complexity of this solution is (O(m \times n)), where (m) is the length of word1 and (n) is the length of word2. This is because we need to fill an (m \times n) DP table.

The space complexity is also (O(m \times n)), which is the space required to store the DP table.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI