✅Beats 100% Solution || 4 Approaches : Recursive || Memoization || Tabulation || Space Optimization
Intuition and ApproachThe solution involves recursion by breaking the problem into smaller subproblems. Here's how it works:
Base Cases
If one string is exhaust
![image.png](https://assets.leetcode.com/users/images/30f2836e-280c-494f-84b2-e838b9556098_1735660615.3672764.png)

# Intuition and Approach
![WhatsApp Image 2025-01-01 at 21.49.55_9e6fccb6.jpg](https://assets.leetcode.com/users/images/7aed3d4b-df17-47b8-9a27-4d61d54904c6_1735749096.746735.jpeg)

The solution involves recursion by breaking the problem into smaller subproblems. Here's how it works:

1. Base Cases
If one string is exhausted (i.e., index1 < 0 or index2 < 0):
    - Case 1: If index1 < 0:
It means word1 is empty, so we need to insert all remaining characters of word2.
Cost: index2 + 1.
    - Case 2: If index2 < 0:
It means word2 is empty, so we need to delete all remaining characters of word1.
Cost: index1 + 1.
2. Recursive Relation
For the current characters of word1 (word1[index1]) and word2 (word2[index2]):

- If the characters match (word1[index1] == word2[index2]):
    - No operation is needed. Simply solve the problem for the rest of the strings:
solve(index1-1, index2-1, word1, word2).

- If the characters do not match: We have three options:

    - Insertion: Insert word2[index2] at the current position of word1. Then, compare index1 with index2 - 1.
        - Cost: 1 + solve(index1, index2-1, word1, word2)
    - Deletion: Delete word1[index1] and compare index1 - 1 with index2.
        - Cost: 1 + solve(index1-1, index2, word1, word2)
    - Replacement: Replace word1[index1] with word2[index2], and compare index1 - 1 with index2 - 1.
        - Cost: 1 + solve(index1-1, index2-1, word1, word2)
3. Take the minimum of these three operations to get the result:
    - min(Insertion, Deletion, Replacement)

# Approach 1 : Recursive Approach
In this approach, we recursively compute the minimum distance by considering all three operations (insertion, deletion, and replacement) for each character of the strings. It has exponential time complexity due to overlapping subproblems.

# Complexity
- Time complexity:$$O(2^n+2^m)$$
- Space complexity:$$O(n+m)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
    int solve(int index1,int index2,string &word1,string &word2){
        if(index1<0){
            return index2+1;
        }
        if(index2<0){
            return index1+1;
        }
        if(word1[index1]==word2[index2]){
            return 0+solve(index1-1,index2-1,word1,word2);
        }
        int insertion=1+solve(index1,index2-1,word1,word2);
        int deletion=1+solve(index1-1,index2,word1,word2);
        int replacement=1+solve(index1-1,index2-1,word1,word2);
        return min(insertion,min(deletion,replacement));
    }
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
        return solve(n1-1,n2-1,word1,word2);
    }
};
```
```Java []
class Solution {
    private int solve(int index1, int index2, String word1, String word2) {
        if (index1 < 0) {
            return index2 + 1;
        }
        if (index2 < 0) {
            return index1 + 1;
        }
        if (word1.charAt(index1) == word2.charAt(index2)) {
            return solve(index1 - 1, index2 - 1, word1, word2);
        }
        int insertion = 1 + solve(index1, index2 - 1, word1, word2);
        int deletion = 1 + solve(index1 - 1, index2, word1, word2);
        int replacement = 1 + solve(index1 - 1, index2 - 1, word1, word2);
        return Math.min(insertion, Math.min(deletion, replacement));
    }

    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        return solve(n1 - 1, n2 - 1, word1, word2);
    }
}

```
```python []
class Solution:
    def solve(self, index1, index2, word1, word2):
        if index1 < 0:
            return index2 + 1
        if index2 < 0:
            return index1 + 1
        if word1[index1] == word2[index2]:
            return self.solve(index1 - 1, index2 - 1, word1, word2)
        insertion = 1 + self.solve(index1, index2 - 1, word1, word2)
        deletion = 1 + self.solve(index1 - 1, index2, word1, word2)
        replacement = 1 + self.solve(index1 - 1, index2 - 1, word1, word2)
        return min(insertion, deletion, replacement)

    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        return self.solve(n1 - 1, n2 - 1, word1, word2)

```

# Approach 2 : Memoization Approach
This is a top-down dynamic programming approach that caches the results of subproblems to avoid redundant computations. It reduces time complexity to O(n*m) by storing previously calculated results in a DP array.

# Complexity
- Time complexity:$$O(n*m)$$
- Space complexity:$$O(n+m)$$[Recursive Stack Space]+$$O(n*m)$$[Dp Array]
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
    int solve(int index1,int index2,string &word1,string &word2,vector<vector<int>> &dp){
        if(index1<0){
            return index2+1;
        }
        if(index2<0){
            return index1+1;
        }
        if(dp[index1][index2]!=-1){
            return dp[index1][index2];
        }
        if(word1[index1]==word2[index2]){
            return 0+solve(index1-1,index2-1,word1,word2,dp);
        }
        int insertion=1+solve(index1,index2-1,word1,word2,dp);
        int deletion=1+solve(index1-1,index2,word1,word2,dp);
        int replacement=1+solve(index1-1,index2-1,word1,word2,dp);
        return dp[index1][index2]=min(insertion,min(deletion,replacement));
    }
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,-1));
        return solve(n1-1,n2-1,word1,word2,dp);
    }
};
```
```Java []
class Solution {
    private int solve(int index1, int index2, String word1, String word2, int[][] dp) {
        if (index1 < 0) {
            return index2 + 1;
        }
        if (index2 < 0) {
            return index1 + 1;
        }
        if (dp[index1][index2] != -1) {
            return dp[index1][index2];
        }
        if (word1.charAt(index1) == word2.charAt(index2)) {
            return dp[index1][index2] = solve(index1 - 1, index2 - 1, word1, word2, dp);
        }
        int insertion = 1 + solve(index1, index2 - 1, word1, word2, dp);
        int deletion = 1 + solve(index1 - 1, index2, word1, word2, dp);
        int replacement = 1 + solve(index1 - 1, index2 - 1, word1, word2, dp);
        return dp[index1][index2] = Math.min(insertion, Math.min(deletion, replacement));
    }

    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1][n2];
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                dp[i][j] = -1;
            }
        }
        return solve(n1 - 1, n2 - 1, word1, word2, dp);
    }
}

```
```python []
class Solution:
    def solve(self, index1, index2, word1, word2, dp):
        if index1 < 0:
            return index2 + 1
        if index2 < 0:
            return index1 + 1
        if dp[index1][index2] != -1:
            return dp[index1][index2]
        if word1[index1] == word2[index2]:
            dp[index1][index2] = self.solve(index1 - 1, index2 - 1, word1, word2, dp)
        else:
            insertion = 1 + self.solve(index1, index2 - 1, word1, word2, dp)
            deletion = 1 + self.solve(index1 - 1, index2, word1, word2, dp)
            replacement = 1 + self.solve(index1 - 1, index2 - 1, word1, word2, dp)
            dp[index1][index2] = min(insertion, deletion, replacement)
        return dp[index1][index2]

    def minDistance(self, word1, word2):
        n1, n2 = len(word1), len(word2)
        dp = [[-1 for _ in range(n2)] for _ in range(n1)]
        return self.solve(n1 - 1, n2 - 1, word1, word2, dp)

```

# Approach 3 : Tabulation Approach
The tabulation approach uses a bottom-up dynamic programming approach, filling a DP table. Starting from the base cases, it computes the minimum distance by considering all possible operations for each pair of substrings.

# Complexity
- Time complexity:$$O(n*m)$$
- Space complexity:$$O(n*m)$$[Dp Array]
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
        for(int i=0;i<n1+1;i++) dp[i][0]=i;
        for(int j=0;j<n2+1;j++) dp[0][j]=j;
        for(int i=1;i<n1+1;i++){
            for(int j=1;j<n2+1;j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }
                else{
                    int insertion=1+dp[i][j-1];
                    int deletion=1+dp[i-1][j];
                    int replacement=1+dp[i-1][j-1];
                    dp[i][j]=min(insertion,min(deletion,replacement));
                }
            }
        }
        return dp[n1][n2];
    }
};
```
```Java []
class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        
        for (int i = 0; i <= n1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n2; j++) {
            dp[0][j] = j;
        }
        
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int insertion = 1 + dp[i][j - 1];
                    int deletion = 1 + dp[i - 1][j];
                    int replacement = 1 + dp[i - 1][j - 1];
                    dp[i][j] = Math.min(insertion, Math.min(deletion, replacement));
                }
            }
        }
        
        return dp[n1][n2];
    }
}

```
```python []
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1, n2 = len(word1), len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        
        for i in range(n1 + 1):
            dp[i][0] = i
        for j in range(n2 + 1):
            dp[0][j] = j
        
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    insertion = 1 + dp[i][j - 1]
                    deletion = 1 + dp[i - 1][j]
                    replacement = 1 + dp[i - 1][j - 1]
                    dp[i][j] = min(insertion, deletion, replacement)
        
        return dp[n1][n2]

```


# Approach 4 : Space Optimization
This approach reduces space complexity by maintaining only two arrays (previous and current rows) instead of the entire DP table. It optimizes memory usage while retaining the O(n*m) time complexity.

# Complexity
- Time complexity:$$O(n*m)$$
- Space complexity:$$O(m+m)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size();
        int n2=word2.size();
        vector<int> prev(n2+1,0),curr(n2+1,0);
        for(int j=0;j<n2+1;j++) prev[j]=j;
        for(int i=1;i<n1+1;i++){
            curr[0]=i;
            for(int j=1;j<n2+1;j++){
                if(word1[i-1]==word2[j-1]){
                    curr[j]=prev[j-1];
                }
                else{
                    int insertion=1+curr[j-1];
                    int deletion=1+prev[j];
                    int replacement=1+prev[j-1];
                    curr[j]=min(insertion,min(deletion,replacement));
                }
            }
            prev=curr;
        }
        return prev[n2];
    }
};
```
```Java []
class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[] prev = new int[n2 + 1];
        int[] curr = new int[n2 + 1];
        
        for (int j = 0; j <= n2; j++) {
            prev[j] = j;
        }
        
        for (int i = 1; i <= n1; i++) {
            curr[0] = i;
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    curr[j] = prev[j - 1];
                } else {
                    int insertion = 1 + curr[j - 1];
                    int deletion = 1 + prev[j];
                    int replacement = 1 + prev[j - 1];
                    curr[j] = Math.min(insertion, Math.min(deletion, replacement));
                }
            }
            prev = curr.clone();
        }
        
        return prev[n2];
    }
}

```
```python []
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1, n2 = len(word1), len(word2)
        prev = [j for j in range(n2 + 1)]
        curr = [0] * (n2 + 1)
        
        for i in range(1, n1 + 1):
            curr[0] = i
            for j in range(1, n2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1]
                else:
                    insertion = 1 + curr[j - 1]
                    deletion = 1 + prev[j]
                    replacement = 1 + prev[j - 1]
                    curr[j] = min(insertion, deletion, replacement)
            prev = curr[:]
        
        return prev[n2]

```


['Dynamic Programming', 'Python', 'C++', 'Java', 'Python3']