# Edit Distance
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/edit-distance)
Canonical: https://scaleengineer.com/dsa/problems/edit-distance
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Deloitte](https://scaleengineer.com/companies/deloitte), [Flipkart](https://scaleengineer.com/companies/flipkart), [Infosys](https://scaleengineer.com/companies/infosys), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nielsen](https://scaleengineer.com/companies/nielsen), [TikTok](https://scaleengineer.com/companies/tiktok), [Visa](https://scaleengineer.com/companies/visa), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [Swiggy](https://scaleengineer.com/companies/swiggy), [HashedIn](https://scaleengineer.com/companies/hashedin), [Axon](https://scaleengineer.com/companies/axon), [Rubrik](https://scaleengineer.com/companies/rubrik), [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
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:

* Insert a character
* Delete a character
* Replace a character

**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.

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's definition into a recursive function. We explore all possible sequences of operations (insert, delete, replace) by considering the last characters of the two strings at each step. The function `solve(i, j)` calculates the edit distance for prefixes `word1[0...i]` and `word2[0...j]` by breaking it down into smaller subproblems.
**Time:** O(3^max(m, n)) · **Space:** O(m + n)
**Pros:** Simple to understand and implement as it directly follows the problem's recursive structure.
**Cons:** Extremely inefficient due to a large number of redundant calculations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for anything but very small inputs.
### Explanation
The core idea is to make a decision at each step based on the last characters of the current prefixes of `word1` and `word2`.

If the characters `word1[i]` and `word2[j]` match, they contribute nothing to the edit distance. The problem reduces to finding the edit distance for the strings without these last characters, which is a recursive call `solve(i-1, j-1)`.

If the characters do not match, we have three choices:
1.  **Insert:** We can insert `word2[j]` into `word1` to match it. The problem then becomes converting `word1[0...i]` to `word2[0...j-1]`. The cost is `1 + solve(i, j-1)`.
2.  **Delete:** We can delete `word1[i]`. The problem becomes converting `word1[0...i-1]` to `word2[0...j]`. The cost is `1 + solve(i-1, j)`.
3.  **Replace:** We can replace `word1[i]` with `word2[j]`. The problem becomes converting `word1[0...i-1]` to `word2[0...j-1]`. The cost is `1 + solve(i-1, j-1)`.

We take the minimum of these three options. The base cases handle situations where one of the strings becomes empty.

```java
class Solution {
    public int minDistance(String word1, String word2) {
        return solve(word1, word2, word1.length() - 1, word2.length() - 1);
    }

    private int solve(String word1, String word2, int i, int j) {
        // Base case: If word1 is empty, we need to insert all characters of word2.
        if (i < 0) {
            return j + 1;
        }
        // Base case: If word2 is empty, we need to delete all characters of word1.
        if (j < 0) {
            return i + 1;
        }

        // If the last characters are the same, no operation is needed.
        if (word1.charAt(i) == word2.charAt(j)) {
            return solve(word1, word2, i - 1, j - 1);
        } else {
            // If last characters are different, consider all three operations.
            int insertOp = solve(word1, word2, i, j - 1);
            int deleteOp = solve(word1, word2, i - 1, j);
            int replaceOp = solve(word1, word2, i - 1, j - 1);
            
            return 1 + Math.min(insertOp, Math.min(deleteOp, replaceOp));
        }
    }
}
```
### Algorithm
*   Define a recursive function `solve(i, j)` that takes two indices representing the end of the prefixes of `word1` and `word2`.
*   **Base Case 1:** If `i` is less than 0 (meaning `word1`'s prefix is empty), we need to insert all remaining characters of `word2`. The cost is `j + 1`.
*   **Base Case 2:** If `j` is less than 0 (meaning `word2`'s prefix is empty), we need to delete all remaining characters of `word1`. The cost is `i + 1`.
*   **Recursive Step (Characters Match):** If `word1.charAt(i)` is the same as `word2.charAt(j)`, no operation is needed for these characters. We simply recurse on the smaller prefixes: `solve(i - 1, j - 1)`.
*   **Recursive Step (Characters Differ):** If the characters are different, we must perform an operation. We explore all three possibilities and take the one with the minimum cost:
    *   **Insert:** `1 + solve(i, j - 1)`
    *   **Delete:** `1 + solve(i - 1, j)`
    *   **Replace:** `1 + solve(i - 1, j - 1)`
*   The initial call to the function is `solve(word1.length() - 1, word2.length() - 1)`.

## Recursion with Memoization (Top-Down DP)
This approach, also known as Top-Down Dynamic Programming, optimizes the brute-force recursion. It uses a 2D array (a memoization table) to store the results of subproblems that have already been solved. When the function is called with the same parameters again, it retrieves the result from the table instead of re-computing it, thus avoiding exponential complexity.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Drastically more efficient than brute-force, with a polynomial time complexity.; Often more intuitive to derive from the recursive solution.
**Cons:** Uses O(m * n) space for the memoization table, which can be large.; Still uses recursion, which has some overhead and a limited stack depth (though not an issue for the given constraints).
### Explanation
We observe that the brute-force recursive solution repeatedly solves the same subproblems (e.g., `solve(i, j)` is called from multiple different paths). Memoization addresses this by caching the results.

We use a 2D array, `memo`, where `memo[i][j]` will store the minimum edit distance between the first `i` characters of `word1` and the first `j` characters of `word2`. The array is initialized with a sentinel value (like -1) to indicate that a state has not been computed.

In our recursive function, the first step is to check the memo table. If a result for the current state `(i, j)` exists, we return it instantly. Otherwise, we perform the same logic as the brute-force approach to compute the result. Crucially, before returning, we save this newly computed result in `memo[i][j]` for future use.

This ensures that each of the `m * n` subproblems is calculated only once.

```java
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] memo = new int[m + 1][n + 1];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return solve(word1, word2, m, n, memo);
    }

    private int solve(String word1, String word2, int i, int j, int[][] memo) {
        if (i == 0) {
            return j;
        }
        if (j == 0) {
            return i;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        int result;
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
            result = solve(word1, word2, i - 1, j - 1, memo);
        } else {
            int insertOp = solve(word1, word2, i, j - 1, memo);
            int deleteOp = solve(word1, word2, i - 1, j, memo);
            int replaceOp = solve(word1, word2, i - 1, j - 1, memo);
            result = 1 + Math.min(insertOp, Math.min(deleteOp, replaceOp));
        }
        
        memo[i][j] = result;
        return result;
    }
}
```
### Algorithm
*   Create a 2D array `memo` of size `(m+1) x (n+1)` to store the results of subproblems, initialized with a value like -1.
*   Define a recursive function `solve(i, j)` that takes the current lengths of the prefixes.
*   **Base Cases:** If `i` is 0, return `j`. If `j` is 0, return `i`.
*   **Memoization Check:** Before computing, check if `memo[i][j]` is not -1. If it's not, return the stored value immediately.
*   **Recursive Step (Characters Match):** If `word1.charAt(i-1) == word2.charAt(j-1)`, the result is `solve(i-1, j-1)`.
*   **Recursive Step (Characters Differ):** Otherwise, the result is `1 + min(solve(i, j-1), solve(i-1, j), solve(i-1, j-1))`.
*   **Store Result:** Before returning the computed result, store it in `memo[i][j]`.
*   The initial call is `solve(m, n)`.

## Tabulation (Bottom-Up DP)
This is the classic iterative or Bottom-Up Dynamic Programming solution. It avoids recursion by systematically building up the solution from the smallest subproblems. A 2D table, `dp`, is used where `dp[i][j]` stores the minimum edit distance to convert the first `i` characters of `word1` to the first `j` characters of `word2`.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Efficient and robust, with no recursion overhead or risk of stack overflow.; The logic is clear and directly models the state transitions.
**Cons:** Requires O(m * n) space, which can be memory-intensive for very long strings.
### Explanation
The tabulation approach constructs the solution iteratively. We create a `dp` table of size `(m+1) x (n+1)`.

First, we establish the base cases. `dp[0][j]` represents converting an empty string to a prefix of `word2` of length `j`, which requires `j` insertions. So, `dp[0][j] = j`. Similarly, `dp[i][0]` represents converting a prefix of `word1` of length `i` to an empty string, requiring `i` deletions. So, `dp[i][0] = i`.

Then, we fill the rest of the table row by row, column by column. To compute `dp[i][j]`, we look at the characters `word1[i-1]` and `word2[j-1]`.
- If they match, the cost is the same as the subproblem for prefixes `i-1` and `j-1`, so `dp[i][j] = dp[i-1][j-1]`.
- If they differ, we need one operation. The total cost will be 1 plus the minimum of the costs of the three preceding states:
    - `dp[i-1][j]`: Cost if we delete `word1[i-1]`.
    - `dp[i][j-1]`: Cost if we insert `word2[j-1]`.
    - `dp[i-1][j-1]`: Cost if we replace `word1[i-1]` with `word2[j-1]`.

The final answer is `dp[m][n]`, which represents the edit distance for the full strings.

```java
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        int[][] dp = new int[m + 1][n + 1];
        
        // Initialize base cases
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // Cost of deleting i chars from word1 to get an empty string
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // Cost of inserting j chars to an empty string to get word2
        }
        
        // Fill the DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int deleteOp = dp[i - 1][j];
                    int insertOp = dp[i][j - 1];
                    int replaceOp = dp[i - 1][j - 1];
                    dp[i][j] = 1 + Math.min(deleteOp, Math.min(insertOp, replaceOp));
                }
            }
        }
        
        return dp[m][n];
    }
}
```
### Algorithm
*   Let `m = word1.length()` and `n = word2.length()`.
*   Create a 2D array `dp` of size `(m+1) x (n+1)`.
*   **Initialize Base Cases:**
    *   Fill the first row: `dp[0][j] = j` for `j` from 0 to `n`. (Cost of insertions)
    *   Fill the first column: `dp[i][0] = i` for `i` from 0 to `m`. (Cost of deletions)
*   **Fill the Table:**
    *   Iterate with `i` from 1 to `m`.
    *   Iterate with `j` from 1 to `n`.
    *   If `word1.charAt(i-1) == word2.charAt(j-1)`:
        *   `dp[i][j] = dp[i-1][j-1]` (No operation cost)
    *   Else:
        *   `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])` (Cost of delete, insert, or replace)
*   The final answer is the value in the bottom-right cell, `dp[m][n]`.

## Space-Optimized Bottom-Up DP
This approach optimizes the space complexity of the bottom-up DP solution from `O(m*n)` to `O(min(m, n))`. It's based on the observation that to compute the values for the current row `i` of the DP table, we only need the values from the previous row `i-1`. Therefore, we don't need to store the entire 2D table, and can make do with a single 1D array.
**Time:** O(m * n) · **Space:** O(min(m, n))
**Pros:** Most efficient solution in terms of space complexity.; Maintains the optimal O(m * n) time complexity.
**Cons:** The logic is more complex to implement correctly due to the need to juggle values from the previous and current rows within a single array.
### Explanation
Instead of a full 2D table, we can use a single 1D array, say `dp`, of size `n+1` (where `n` is the length of the shorter string to save space). This `dp` array will be used to compute the current row's values based on the previous row's values which it already holds.

When we compute `dp[j]` (representing the cell `(i, j)` in the 2D version), we need:
1.  `dp[i][j-1]` (Insert): This is `dp[j-1]` in our 1D array, which has just been computed for the current row `i`.
2.  `dp[i-1][j]` (Delete): This is the value that `dp[j]` held *before* we started computing the current row `i`. We save this in a `temp` variable.
3.  `dp[i-1][j-1]` (Replace/Match): This was the value of `dp[j-1]` from the previous row. We use another variable, `prev_val`, to track this diagonal value as we iterate across the row.

By carefully managing `prev_val` and a `temp` variable inside the inner loop, we can simulate the 2D table's calculations using only one array.

```java
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // Ensure word2 is the shorter string to optimize space
        if (m < n) {
            // Swap strings and lengths to call recursively
            return minDistance(word2, word1);
        }

        // Now m >= n. We use an array of size n+1.
        int[] dp = new int[n + 1];

        // Initialize the dp array as if word1 is empty
        for (int j = 0; j <= n; j++) {
            dp[j] = j;
        }

        // Iterate through word1
        for (int i = 1; i <= m; i++) {
            int prev_val = dp[0]; // This is dp[i-1][j-1] for j=1
            dp[0] = i; // Base case for the current row i

            // Iterate through word2
            for (int j = 1; j <= n; j++) {
                int temp = dp[j]; // This is dp[i-1][j]
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev_val;
                } else {
                    // dp[j-1] is dp[i][j-1] (insert)
                    // temp is dp[i-1][j] (delete)
                    // prev_val is dp[i-1][j-1] (replace)
                    dp[j] = 1 + Math.min(dp[j - 1], Math.min(temp, prev_val));
                }
                prev_val = temp;
            }
        }

        return dp[n];
    }
}
```
### Algorithm
*   To minimize space, ensure `word2` is the shorter string (if not, swap the strings). Let `m` be the length of the longer string and `n` be the length of the shorter one.
*   Create a 1D array `dp` of size `n+1`.
*   Initialize `dp` as the first row of the conceptual 2D table: `dp[j] = j` for `j` from 0 to `n`.
*   Iterate `i` from 1 to `m` (for each character of the longer string):
    *   Store the top-left diagonal value needed for the first column calculation: `prev_val = dp[0]`.
    *   Update the first element of the current row: `dp[0] = i`.
    *   Iterate `j` from 1 to `n`:
        *   Store the value from the previous row, `dp[j]`, in a `temp` variable before it's overwritten. This is the `dp[i-1][j]` value.
        *   If `word1.charAt(i-1) == word2.charAt(j-1)`, then `dp[j] = prev_val`.
        *   Else, `dp[j] = 1 + min(dp[j-1], temp, prev_val)`.
        *   Update `prev_val = temp` to be used in the next `j` iteration as the new diagonal value.
*   Return `dp[n]`.

# Solutions
### Java

```java
class Solution {
public
  int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] f = new int[m + 1][n + 1];
    for (int j = 1; j <= n; ++j) {
      f[0][j] = j;
    }
    for (int i = 1; i <= m; ++i) {
      f[i][0] = i;
      for (int j = 1; j <= n; ++j) {
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
          f[i][j] = f[i - 1][j - 1];
        } else {
          f[i][j] =
              Math.min(f[i - 1][j], Math.min(f[i][j - 1], f[i - 1][j - 1])) + 1;
        }
      }
    }
    return f[m][n];
  }
}

```

### JavaScript

```javascript
/** * @param {string} word1 * @param {string} word2 * @return {number} */ var minDistance =
  function (word1, word2) {
    const m = word1.length;
    const n = word2.length;
    const f = Array(m + 1)
      .fill(0)
      .map(() => Array(n + 1).fill(0));
    for (let j = 1; j <= n; ++j) {
      f[0][j] = j;
    }
    for (let i = 1; i <= m; ++i) {
      f[i][0] = i;
      for (let j = 1; j <= n; ++j) {
        if (word1[i - 1] === word2[j - 1]) {
          f[i][j] = f[i - 1][j - 1];
        } else {
          f[i][j] = Math.min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1;
        }
      }
    }
    return f[m][n];
  };

```

### CPP

```cpp
class Solution {
public:
  int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    int f[m + 1][n + 1];
    for (int j = 0; j <= n; ++j) {
      f[0][j] = j;
    }
    for (int i = 1; i <= m; ++i) {
      f[i][0] = i;
      for (int j = 1; j <= n; ++j) {
        if (word1[i - 1] == word2[j - 1]) {
          f[i][j] = f[i - 1][j - 1];
        } else {
          f[i][j] = min({f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]}) + 1;
        }
      }
    }
    return f[m][n];
  }
};

```

### Python

```python
class Solution:
    # dp[i - 1][j - 1]) meaning replace. # e.g. "abc" and "bf", checking "ab" and "b" distance, # then replace either way for "c" or "f" dp [ i ][ j ] = 1 + min ( dp [ i ][ j - 1 ], dp [ i - 1 ][ j ], dp [ i - 1 ][ j - 1 ]) return dp [ - 1 ][ - 1 ] ############ class Solution : def minDistance ( self , word1 : str , word2 : str ) -> int : m , n = len ( word1 ), len ( word2 ) f = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] for j in range ( 1 , n + 1 ): f [ 0 ][ j ] = j for i , a in enumerate ( word1 , 1 ): f [ i ][ 0 ] = i # merged for loops from above solution, but not good for readability for j , b in enumerate ( word2 , 1 ): if a == b : f [ i ][ j ] = f [ i - 1 ][ j - 1 ] else : f [ i ][ j ] = min ( f [ i - 1 ][ j ], f [ i ][ j - 1 ], f [ i - 1 ][ j - 1 ]) + 1 return f [ m ][ n ]
    def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else:

```