🌱 Keegan's Digital Garden

72. Edit Distance

3 min read

📝 Problem Details

input strings word1 word2 return the minimum number of operations required to convert word1 to word2 available operations: insert a character delete a character replace a character

💭What Were My Initial Thoughts?

- seems like an enumeration backtracking problem where every choice has 3 possible options
- a DFS recursive backtracking approach would result in a worst case of O(3^n)
- we could possibly cache results with the use of memoization 
- we could also come up with a bottom up approach to avoid caching

💡 Explanation of Solution

1. Subproblem:
	- we need to transform s1 and s2 using the minimum number of operations
	- the minimum number of operations to transform substrings in s1 and s2 can be used to determine the result of the entire input

2. Topdown - BottomUp
	- opting for a bottom up approach

3. Define State:
	- let dp[i][j] be the min operations required to convert the first i chars of s1 into the first j chars of s2

4. State Transition:
	- base cases:
		- dp[0][j] = j --> if s1 is empty, we need j insertions
		- dp[0][i] = i --> if s2 is empty, we need i deletions

	- If s1[i-1] == s2[j-1] --> No operation needed, carry over dp[i-1][j-1]
	- Otherwise, take the minimum of:
	  1. Insert --> dp[i][j-1] + 1 → (Make s1 longer)
	  2. Delete --> dp[i-1][j] + 1 → (Remove a character from s1)
	  3. Replace --> dp[i-1][j-1] + 1 → (Modify s1[i] to match s2[j])

	dp[i][j] = min(
		dp[i-1][j] + 1, // delete
		dp[i][j-1] + 1, // insert
		dp[i-1][j-1] + (s1[i-1] != s2[i-1]) // Replace (only if chars arent the same)
	);

⌛ Complexity Analysis

Time Complexity: O(m * n)
Space Complexity: O(m * n)

💻 Implementation of Solution

class Solution {
public:
    int minDistance(string s1, string s2) {
        int n = s1.size(), m = s2.size();
 
        // Create a DP table where dp[i][j] represents the minimum number of operations
        // needed to convert the first i characters of s1 to the first j characters of s2.
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
 
        // Base Cases:
        // If s1 is empty, we need to insert all characters of s2
        for (int j = 0; j <= m; j++) dp[0][j] = j;
 
        // If s2 is empty, we need to delete all characters of s1
        for (int i = 0; i <= n; i++) dp[i][0] = i;
 
        // Fill the DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    // If the characters are the same, carry over the previous value
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // If characters are different, we consider:
                    // - Insert a character (dp[i][j-1] + 1)
                    // - Delete a character (dp[i-1][j] + 1)
                    // - Replace a character (dp[i-1][j-1] + 1)
                    dp[i][j] = min({
                        dp[i - 1][j] + 1,   // Delete
                        dp[i][j - 1] + 1,   // Insert
                        dp[i - 1][j - 1] + 1  // Replace
                    });
                }
            }
        }
 
        // The final answer is in dp[n][m], meaning the min operations needed to transform s1 -> s2
        return dp[n][m];
    }
};

Graph View