DP Solution Completely Explained - 3 approaches - Memoization , Tabulation and Space Optimisation 
IntuitionThe Problem asks to convert a String (word1) to another String (word 2) and so we need to perform some operations in order to achieve the goal . If two
# Intuition
The Problem asks to convert a String (word1) to another String (word 2) and so we need to perform some operations in order to achieve the goal . If two strings are already identical, no operations are needed. However, if they differ, we must transform word1 into word2 with the least number of edits. This suggests an optimal substructure, where the solution to a big problem depends on solving smaller subproblems.
The options of operations are :- 
1. **Insert a character** (make word1 longer to match word2).

2. **Delete a character** (make word1 shorter).

3. **Replace a character** (replace a character in word1 to match word2)



# Approach
As we can break the problem in **overlapping subproblems** and also the constraints are light, we can apply **Dynamic Programming**. 
So i tried to first solve the problem with recursion and once it is solved, i used **caching (Memoization)** to reduce redundant calculations and made the code optimal.
### Memoization (Top-Down DP with Recursion)
Firstly we try to build the recursive solution and for that we took 2 pointers to iterate seperately over the two Strings. Then i defined the base cases :- 
**1) If i(for word1) goes out of bound, insert all remaining characters of word1 that are to be matched with that of word2.**
**2) If j(for word2) goes out of bound, delete all remaining characters in word1.**

After tackling the base case, if **word1[i] == word2[j]** then return number of operations to convert word1[i+1:] into word2[j+1:], i.e. number of operations to convert remaining word1 to remaining word2, as no operations are needed to make word1[i] == word2[j] because they are already equal.
But if **word1[i] != word2[j]** then,
1) **Insert a character** -> j increments only, as we assume we inserted word1[j] in word2 and then check whether remaining word2 matches remaining word1.
2) **Delete a character** -> i increments only, as we assume we deleted the character at position i in word1 and checks whether remaining word1 matches word2.
3) **Replace a Character** -> increments both i adn j assuming we replace word1[i] with word2[j] at i in word1 and checks for string matching in remaining word1 and word2.

After getting minimum of the above three operations we add 1 **(signifying that we performed an operation)** and then return it.

# Complexity
- Time complexity :-> **O(m × n)**

- Space complexity :-> **O(m × n)**

# Code
```python3 []
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = {}
        def solve(i, j):
            #Delete all the remaining chars in the String 1
            if j == len(word2):
                return len(word1) - i
            #Insert all the remaining characters to String 1
            elif i == len(word1):
                return len(word2) - j
            if (i, j) in dp:
                return dp[(i, j)]
            #If chars from both strings match
            if word1[i] == word2[j]:
                dp[(i, j)] = solve(i+1, j+1)
                return dp[(i, j)]
            dp[(i, j)] = 1 + min(
                solve(i, j+1), #Insertion
                solve(i+1, j), #Deletion
                solve(i+1, j+1)) #Replace
            return dp[(i, j)]
        return solve(0, 0)
```
``` Javascript []
"use strict";

class Solution {
    minDistance(word1, word2) {
        let dp = {};
        function solve(i, j) {
            //Delete all the remaining chars in the String 1
            if (j === word2.length) {
                return word1.length - i;
            }
            //Insert all the remaining characters to String 1
            else if (i === word1.length) {
                return word2.length - j;
            }
            let key = i + "," + j;
            if (dp.hasOwnProperty(key)) {
                return dp[key];
            }
            //If chars from both strings match
            if (word1[i] === word2[j]) {
                dp[key] = solve(i+1, j+1);
                return dp[key];
            }
            dp[key] = 1 + Math.min(
                solve(i, j+1), //Insertion
                solve(i+1, j), //Deletion
                solve(i+1, j+1) //Replace
            );
            return dp[key];
        }
        return solve(0, 0)
    }
}
```
``` Java []
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Solution {
    public int minDistance(String word1, String word2) {
        Map<Key, Integer> dp = new HashMap<>();
        return solve(0, 0, word1, word2, dp);
    }

    private int solve(int i, int j, String word1, String word2, Map<Key, Integer> dp) {
        //Delete all the remaining chars in the String 1
        if (j == word2.length()) {
            return word1.length() - i;
        }
        //Insert all the remaining characters to String 1
        else if (i == word1.length()) {
            return word2.length() - j;
        }
        Key key = new Key(i, j);
        if (dp.containsKey(key)) {
            return dp.get(key);
        }
        //If chars from both strings match
        if (word1.charAt(i) == word2.charAt(j)) {
            dp.put(key, solve(i + 1, j + 1, word1, word2, dp));
            return dp.get(key);
        }
        dp.put(key, 1 + Math.min(
                solve(i, j + 1, word1, word2, dp), //Insertion
                Math.min(
                        solve(i + 1, j, word1, word2, dp), //Deletion
                        solve(i + 1, j + 1, word1, word2, dp) //Replace
                )
        ));
        return dp.get(key);
    }

    // Key class for memoization map
    private static class Key {
        int i;
        int j;

        public Key(int i, int j) {
            this.i = i;
            this.j = j;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Key key = (Key) o;
            return i == key.i && j == key.j;
        }

        @Override
        public int hashCode() {
            return Objects.hash(i, j);
        }
    }
}
```
``` C++ []
#include <string>
#include <unordered_map>
#include <functional>
#include <algorithm>
#include <utility>
using namespace std;

// Hash function for pair<int, int>
struct pair_hash {
    size_t operator()(const pair<int, int>& p) const {
        auto hash1 = hash<int>()(p.first);
        auto hash2 = hash<int>()(p.second);
        return hash1 ^ (hash2 << 1);
    }
};

class Solution {
public:
    int minDistance(string word1, string word2) {
        unordered_map<pair<int, int>, int, pair_hash> dp;
        // Define the lambda function 'solve' which takes two indices i and j
        function<int(int, int)> solve = [&](int i, int j) -> int {
            //Delete all the remaining chars in the String 1
            if (j == word2.length()) {
                return word1.length() - i;
            }
            //Insert all the remaining characters to String 1
            else if (i == word1.length()) {
                return word2.length() - j;
            }
            if (dp.find({i, j}) != dp.end()) {
                return dp[{i, j}];
            }
            //If chars from both strings match
            if (word1[i] == word2[j]) {
                dp[{i, j}] = solve(i + 1, j + 1);
                return dp[{i, j}];
            }
            dp[{i, j}] = 1 + min({ solve(i, j + 1), //Insertion
                                   solve(i + 1, j), //Deletion
                                   solve(i + 1, j + 1) }); //Replace
            return dp[{i, j}];
        };
        return solve(0, 0);
    }
};
```

### Tabulation (Bottom-Up DP with 2D Array)
For tabulation i created a 2-D Array representing **Minimum operations to turn word1[0:j] to word2[0:i].** 
Then handeled the Base cases by two loops to assign values at i == 0 and j == 0. If i == 0 then the number of characters in word1 should be deleted and if j == 0 then the number of characters in word2 should be added to word1.
Then the nested loop is used to replicate the operations performed in memoization.

# Complexity
- Time complexity :-> **O(m × n)**

- Space complexity :-> **O(m × n) (No Recursion overhead)**

# Code
```python3 []
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        #Initialise DP array
        dp = [[0] * (n+1) for _ in range(m+1)]
        #If i==0 assign number of characters in word1[0:j]
        for j in range(1, n+1):
            dp[0][j] = j
        #If j==0 assign number of characters in word2[0:i]
        for i in range(1, m+1):
            dp[i][0] = i

        for i in range(1, m+1):
            for j in range(1, n+1):
                #If chars matches
                if word2[i-1] == word1[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(
                        dp[i][j-1],
                        dp[i-1][j],
                        dp[i-1][j-1]
                    )
        return dp[m][n]
```
``` C++ []
#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
        int n = word1.length(), m = word2.length();
        // Initialise DP array
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
        // If i==0 assign number of characters in word1[0:j]
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = j;
        }
        // If j==0 assign number of characters in word2[0:i]
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                // If chars match
                if (word2[i - 1] == word1[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + std::min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]});
                }
            }
        }
        return dp[m][n];
    }
};
```
``` Java []
import java.util.Arrays;

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        // Initialise DP array
        int[][] dp = new int[m + 1][n + 1];
        // If i==0 assign number of characters in word1[0:j]
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        // If j==0 assign number of characters in word2[0:i]
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If chars match
                if (word2.charAt(i - 1) == word1.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(
                        Math.min(dp[i][j - 1], dp[i - 1][j]),
                        dp[i - 1][j - 1]
                    );
                }
            }
        }
        return dp[m][n];
    }
}
```
``` Javascript []
"use strict";

// No external dependencies or imports are required for this code.

class Solution {
    minDistance(word1, word2) {
        let n = word1.length, m = word2.length;
        //Initialise DP array
        let dp = new Array(m + 1);
        for (let i = 0; i <= m; i++) {
            dp[i] = new Array(n + 1).fill(0);
        }
        //If i==0 assign number of characters in word1[0:j]
        for (let j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        //If j==0 assign number of characters in word2[0:i]
        for (let i = 1; i <= m; i++) {
            dp[i][0] = i;
        }

        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                //If chars matches
                if (word2[i - 1] === word1[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(
                        dp[i][j - 1],
                        dp[i - 1][j],
                        dp[i - 1][j - 1]
                    );
                }
            }
        }
        return dp[m][n];
    }
}
```
### 1-D Array Space Optimised
As we can see at any given time, we will only need either the current row or the previous row for calculating current results, so we can space optimise it by only storing the previous row and having an array inside the loop to depict the current row.

# Complexity
- Time complexity :-> **O(m × n)**

- Space complexity :-> **O(n)**

# Code
```python3 []
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        #Depicts the previous row 
        dp = [i for i in range(n+1)]
        for i in range(1, m+1):
            #current row
            curr = [0] * (n+1)
            curr[0] = i
            for j in range(1, n+1):
                if word1[j-1] == word2[i-1]:
                    curr[j] = dp[j-1]
                else:
                    curr[j] = 1 + min(dp[j], dp[j-1], curr[j-1])
            dp = curr
        return dp[n]
```
``` Java []
class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        // Depicts the previous row
        int[] dp = new int[n + 1];
        
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
        }

        for (int i = 1; i <= m; i++) {
            // Current row
            int[] curr = new int[n + 1];
            curr[0] = i;
            
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(j - 1) == word2.charAt(i - 1)) {
                    curr[j] = dp[j - 1];
                } else {
                    curr[j] = 1 + Math.min(dp[j], Math.min(dp[j - 1], curr[j - 1]));
                }
            }
            dp = curr;
        }
        return dp[n];
    }
}
```
``` JavaScript []
class Solution {
    minDistance(word1, word2) {
        const n = word1.length, m = word2.length;
        // Depicts the previous row 
        let dp = Array.from({ length: n + 1 }, (_, i) => i);
        for (let i = 1; i <= m; i++) {
            // current row
            let curr = new Array(n + 1).fill(0);
            curr[0] = i;
            for (let j = 1; j <= n; j++) {
                if (word1[j - 1] === word2[i - 1]) {
                    curr[j] = dp[j - 1];
                } else {
                    curr[j] = 1 + Math.min(dp[j], dp[j - 1], curr[j - 1]);
                }
            }
            dp = curr;
        }
        return dp[n];
    }
}
```
``` C++ []
#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
        int n = word1.length(), m = word2.length();
        // Depicts the previous row 
        std::vector<int> dp(n + 1);
        for (int i = 0; i <= n; ++i) {
            dp[i] = i;
        }
        for (int i = 1; i <= m; ++i) {
            // current row
            std::vector<int> curr(n + 1);
            curr[0] = i;
            for (int j = 1; j <= n; ++j) {
                if (word1[j - 1] == word2[i - 1]) {
                    curr[j] = dp[j - 1];
                } else {
                    curr[j] = 1 + std::min({dp[j], dp[j - 1], curr[j - 1]});
                }
            }
            dp = curr;
        }
        return dp[n];
    }
};
```

# If you find this post helpful , Please consider UPVOTING 🙏🙏🙏
### If you solved this one, then try *Wildcard Matching* https://leetcode.com/problems/wildcard-matching/solutions/6570533/dp-on-strings-explained-in-detail-3-appr-0s9p/
['String', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++', 'Java', 'Python3', 'JavaScript']