Diagram Explanation Recursion + Memoization + DP O(3^n) to O(N*M)
Recursive Solution (Naive Approach)\n## How ?\n\n1. Pure Recursive Approach (PureRecursive function):\nThe PureRecursive function calculates the minimum edit di
# Recursive Solution (Naive Approach)\n## How ?\n\n1. Pure Recursive Approach (`PureRecursive` function):\nThe `PureRecursive` function calculates the minimum edit distance between two strings `word1` and `word2` using a purely recursive approach. It tries to find the minimum number of operations (insert, delete, or replace) required to convert `word1` into `word2`. The function starts from the last characters of both strings and recursively checks if the characters are the same or different. If they are the same, it moves to the previous characters and continues the comparison. If they are different, it explores all three possible operations (insert, delete, replace) and calculates the minimum distance for each case. The function returns the minimum distance obtained.\n\nTime complexity: Exponential. Since for each character in `word1`, the function has three recursive calls (insert, delete, replace), the time complexity grows exponentially with the length of the strings.\n\nSpace complexity: O(m+n), where \'m\' is the length of `word1` and \'n\' is the length of `word2`. The space complexity is determined by the depth of the recursive calls and the maximum size of the function call stack.\n\n```\nint PureRecursive(string &word1, string &word2,int m, int n){\n        if(m == 0) return n;\n        if(n == 0) return m;\n        if(word1[m-1] == word2[n-1]){\n            return PureRecursive(word1,word2,m-1,n-1);\n        }\n        else{\n            return 1 + min(PureRecursive(word1,word2,m-1,n-1),min(PureRecursive(word1,word2,m-1,n),PureRecursive(word1,word2,m,n-1)));\n        }\n    }\n    int minDistance(string word1, string word2) {\n        vector<vector<int>> dp(word1.size() + 1, std::vector<int>(word2.size() + 1, -1));\n        return bottomUpDp(word1,word2,word1.size(),word2.size(),dp);\n    }\n};\n\n```\n\n# Memoization Approach\n\n## How?\nThe given function `recur` is a recursive solution to the Minimum Edit Distance problem with memoization  (also known as memoization). It calculates the minimum edit distance between two strings `word1` and `word2`.\n\nThe function takes the following parameters:\n- `word1`: A reference to the first string.\n- `word2`: A reference to the second string.\n- `m`: The current index in `word1` (0-based).\n- `n`: The current index in `word2` (0-based).\n- `dp`: A 2D vector representing the memoization table to store intermediate results.\n\nThe idea behind the memoization approach is to store the results of subproblems in the `dp` table to avoid redundant computations. This way, if we encounter the same subproblem during the recursion, we can directly use the precomputed value from the `dp` table instead of recalculating it.\n\nHere\'s how the function works:\n1. Base cases:\n   - If `m` (index in `word1`) becomes 0, it means we have processed all characters in `word1`, so we return the remaining length of `word2` (`n`). This is because, at this point, we would need to insert `n` characters from `word2` into `word1` to match them.\n   - If `n` (index in `word2`) becomes 0, it means we have processed all characters in `word2`, so we return the remaining length of `word1` (`m`). This is because, at this point, we would need to delete `m` characters from `word1` to match them with the empty string.\n\n2. Check if the result for the current subproblem exists in the `dp` table (`dp[m - 1][n - 1]`). If it does, we directly return the precomputed value, avoiding redundant computation.\n\n3. If the characters at the current indices (`word1[m - 1]` and `word2[n - 1]`) are equal, it means no edit is required, and we can move on to the previous characters (index `m - 1` and `n - 1`) to find the solution for the subproblem. We recursively call `recur(word1, word2, m - 1, n - 1, dp)` to compute the minimum edit distance for this case.\n\n4. If the characters at the current indices are different, it means we have three options: insert, delete, or replace a character to make the strings similar. We recursively call `recur` for each option and compute the minimum edit distance among them. The result is stored in the `dp` table (`dp[m - 1][n - 1]`) for future reference.\n\n5. Finally, we return the computed value for the current subproblem.\n\nOverall, the memoization approach reduces the time complexity by avoiding redundant calculations of the same subproblems and improves the performance compared to the pure recursive solution.\n\nPlease note that before calling the `recur` function, you need to initialize the `dp` table with `-1` to indicate that the results for subproblems are not yet computed. The `minDistance` function takes care of this initialization and calls the `recur` function with the appropriate arguments.\n\nMemoizationn Table:\n\n\n|     | e | x | e | c | u | t | i | o | n |\n|-----|---|---|---|---|---|---|---|---|---|\n| i   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n| n   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n| t   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n| e   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n| n   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n| t   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n| i   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n| o   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n| n   | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |\n\nIn this table, the headers for both rows and columns represent the characters from "intention" and "execution." The cells are filled with -1, indicating that the minimum edit distance has not been computed for any of the substrings yet.\n\nConverts to :\n<body>\n    <table>\n        <tr>\n            <td></td>\n            <td>e</td>\n            <td>x</td>\n            <td>e</td>\n            <td>c</td>\n            <td>u</td>\n            <td>t</td>\n            <td>i</td>\n            <td>o</td>\n            <td>n</td>\n            <td>-</td>\n        </tr>\n        <tr>\n            <td>i</td>\n            <td>1</td>\n            <td>2</td>\n            <td>3</td>\n            <td>4</td>\n            <td>5</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>n</td>\n            <td>2</td>\n            <td>2</td>\n            <td>3</td>\n            <td>4</td>\n            <td>5</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>t</td>\n            <td>3</td>\n            <td>3</td>\n            <td>3</td>\n            <td>4</td>\n            <td>5</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>e</td>\n            <td>3</td>\n            <td>4</td>\n            <td>3</td>\n            <td>4</td>\n            <td>5</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>n</td>\n            <td>4</td>\n            <td>4</td>\n            <td>4</td>\n            <td style="background-color: grey">4</td>\n            <td>5</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>t</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td>5</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>i</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td>5</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>o</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td>5</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>n</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: skyblue; color : black;">5<sup>(m-1,n-1)</sup></td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n        <tr>\n            <td>-</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n            <td style="background-color: grey">-1</td>\n        </tr>\n    </table>\n</body>\n</html>\n\nMemoization Solution\n\n```\nint Memoization(string &word1, string &word2,int m, int n,vector<vector<int>>&mem){\n            if (m == 0)\n                return n; //If the word1 length becomes zero, obvious that we are left with the cost of n\n            if (n == 0)\n                return m; //If the word2 length becomes zero, obvious that we are left with the cost of m\n\n            if (mem[m - 1][n - 1] != -1)\n                return mem[m - 1][n - 1];\n\n            if (word1[m - 1] == word2[n - 1])\n            {\n                mem[m - 1][n - 1] = Memoization(word1, word2, m - 1, n - 1, mem);\n                return mem[m - 1][n - 1];\n            }\n            else\n            {\n                mem[m - 1][n - 1] = 1 + min(Memoization(word1, word2, m - 1, n - 1, mem), min(Memoization(word1, word2, m - 1, n, mem), Memoization(word1, word2, m, n - 1, mem)));\n                return mem[m - 1][n - 1];\n            }\n        }\n\n```\n\n# DP Solution :\n## How ?\n1. Bottom-Up Dynamic Programming Approach (`minDistance` function):\nThe `minDistance` function calculates the minimum edit distance between two strings `word1` and `word2` using the Bottom-Up Dynamic Programming approach. It creates a DP table (2D array) of size `(m+1) x (n+1)` to store the minimum edit distance values for all subproblems.\n\nThe idea behind the Bottom-Up DP approach is to fill the DP table from smaller subproblems to the larger ones iteratively, avoiding redundant computations. The DP table `dp[i][j]` represents the minimum edit distance between the first `i` characters of `word1` and the first `j` characters of `word2`.\n\nThe DP table is filled in a bottom-up manner as follows:\n- For `i = 0` or `j = 0`, `dp[i][j]` is initialized to `i` or `j`, respectively. This is because the minimum edit distance between an empty string and a string of length \'x\' is \'x\' (number of insertions or deletions needed).\n- For `i > 0` and `j > 0`, if `word1[i-1]` is equal to `word2[j-1]`, then there is no edit needed, and `dp[i][j]` is set to `dp[i-1][j-1]`.\n- If `word1[i-1]` is not equal to `word2[j-1]`, then `dp[i][j]` is calculated as the minimum of three cases: \n    1. Replace: `1 + dp[i-1][j-1]`\n    2. Insert: `1 + dp[i][j-1]`\n    3. Delete: `1 + dp[i-1][j]`\n\nThe final answer is stored in `dp[m][n]`, which represents the minimum edit distance between the entire `word1` and `word2`.\n\nTime complexity: O(m * n), where \'m\' is the length of `word1` and \'n\' is the length of `word2`. The DP table is filled iteratively in a bottom-up manner, so each cell takes constant time to compute.\n\nSpace complexity: O(m * n), where \'m\' is the length of `word1` and \'n\' is the length of `word2`. The DP table of size `(m+1) x (n+1)` is used to store the intermediate results.\nTable will look like this after the Complete assignment\n<body>\n    <table>\n        <tr>\n            <th> </th>\n            <th>0</th>\n            <th>1</th>\n            <th>2</th>\n            <th>3</th>\n            <th>4</th>\n            <th>5</th>\n            <th>6</th>\n            <th>7</th>\n            <th>8</th>\n            <th>9</th>\n        </tr>\n        <tr>\n            <th>0</th>\n            <td>0</td>\n            <td>1</td>\n            <td>2</td>\n            <td>3</td>\n            <td>4</td>\n            <td>5</td>\n            <td>6</td>\n            <td>7</td>\n            <td>8</td>\n            <td>9</td>\n        </tr>\n        <tr>\n            <th>1</th>\n            <td>1</td>\n            <td style="background-color: gray; color: black;">1</td>\n            <td>2</td>\n            <td>3</td>\n            <td>4</td>\n            <td>5</td>\n            <td>6</td>\n            <td>6</td>\n            <td>7</td>\n            <td>8</td>\n        </tr>\n        <tr>\n            <th>2</th>\n            <td>2</td>\n            <td>2</td>\n            <td style="background-color: gray; color: black;">2</td>\n            <td>3</td>\n            <td>4</td>\n            <td>5</td>\n            <td>6</td>\n            <td>7</td>\n            <td>7</td>\n            <td>7</td>\n        </tr>\n        <tr>\n            <th>3</th>\n            <td>3</td>\n            <td>3</td>\n            <td>3</td>\n            <td style="background-color: gray; color: black;">3</td>\n            <td>4</td>\n            <td>5</td>\n            <td>5</td>\n            <td>6</td>\n            <td>7</td>\n            <td>8</td>\n        </tr>\n        <tr>\n            <th>4</th>\n            <td>3</td>\n            <td>4</td>\n            <td>3</td>\n            <td>4</td>\n            <td style="background-color: gray; color: black;">4</td>\n            <td>5</td>\n            <td>6</td>\n            <td>6</td>\n            <td>7</td>\n            <td>8</td>\n        </tr>\n        <tr>\n            <th>5</th>\n            <td>4</td>\n            <td>4</td>\n            <td>4</td>\n            <td>4</td>\n            <td>4</td>\n            <td style="background-color: gray; color: black;">5</td>\n            <td>6</td>\n            <td>7</td>\n            <td>7</td>\n            <td>7</td>\n        </tr>\n        <tr>\n            <th>6</th>\n            <td>5</td>\n            <td>5</td>\n            <td>5</td>\n            <td>5</td>\n            <td>5</td>\n            <td>5</td>\n            <td style="background-color: gray; color: black;">6</td>\n            <td>7</td>\n            <td>8</td>\n            <td>8</td>\n        </tr>\n        <tr>\n            <th>7</th>\n            <td>6</td>\n            <td>6</td>\n            <td>6</td>\n            <td>6</td>\n            <td>6</td>\n            <td>6</td>\n            <td>6</td>\n            <td style="background-color: gray; color: black;">5</td>\n            <td>6</td>\n            <td>7</td>\n        </tr>\n        <tr>\n            <th>8</th>\n            <td>7</td>\n            <td>7</td>\n            <td>7</td>\n            <td>7</td>\n            <td>7</td>\n            <td>7</td>\n            <td>7</td>\n            <td>6</td>\n            <td style="background-color: gray; color: black;">5</td>\n            <td>6</td>\n        </tr>\n        <tr>\n            <th>9</th>\n            <td>8</td>\n            <td>8</td>\n            <td>8</td>\n            <td>8</td>\n            <td>8</td>\n            <td>8</td>\n            <td>8</td>\n            <td>7</td>\n            <td>6</td>\n            <td style="background-color: skyblue; color : black;">5<sup>(m,n)</sup></td>\n        </tr>\n    </table>\n</body>\n</html>\n\n## Code :\n\n```\nclass Solution {\npublic:\n    int bottomUpDp(string &word1, string &word2, int m, int n, vector<vector<int>>& dp){\n        // Initialize base cases\n        for (int i = 0; i <= m; i++) {\n            dp[i][0] = i;   //rows\n        }\n        for (int j = 0; j <= n; j++) {\n            dp[0][j] = j;   //columns\n        }\n\n        for (int i = 1; i <= m; i++) {\n            for (int j = 1; j <= n; j++) {\n                if (word1[i - 1] == word2[j - 1]) {\n                    dp[i][j] = dp[i - 1][j - 1];\n                } else {\n                    dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));\n                // Carefully observe the recursive code is converted to iterative approach which tries to find the solution in dp table instead of recursive calls\n                }\n            }\n\n        }\n\n        return dp[m][n];\n    }\n\n```
['String', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']