110.1 (Approach 1) | O(m * n))✅ | Python & C++(Step by step explanation)✅
Intuition\nOur goal is to find the minimum number of operations required to convert one word to another. We can achieve this by using dynamic programming. \n\n#
# Intuition\nOur goal is to find the minimum number of operations required to convert one word to another. We can achieve this by using dynamic programming. \n\n# Approach\n\nWe\'ll utilize a dynamic programming approach to solve this problem. We\'ll define a 2D array `dp` where `dp[i][j]` represents the minimum number of operations required to convert the substring `w1[:i]` to the substring `w2[:j]`.\n![image.png](https://assets.leetcode.com/users/images/a23d1c1b-fdaf-417b-b5b3-3ae83f864b8e_1708875109.1336176.png)\n\n\n## Step 1: Define Dynamic Programming Array\nReason: We initialize the `dp` array with dimensions `(len(w1) + 1) \xD7 (len(w2) + 1)`, where `dp[i][j]` represents the minimum number of operations required to convert `w1[:i]` to `w2[:j]`.\n\n## Step 2: Handle Base Cases\nReason: We handle the base cases where one of the strings is empty (`i == 0` or `j == 0`). For `i == 0`, it means `w1` is empty, so the minimum number of operations to convert an empty string to `w2[:j]` is `j`, which corresponds to inserting `j` characters from `w2`. Similarly, for `j == 0`, it means `w2` is empty, so the minimum number of operations to convert `w1[:i]` to an empty string is `i`, which corresponds to deleting `i` characters from `w1`.\n![image.png](https://assets.leetcode.com/users/images/49cabf53-3268-478e-95de-6c690bc44c99_1708875190.3675153.png)\n\n\n## Step 3: Populate DP Array\nReason: We populate the `dp` array iteratively using bottom-up dynamic programming. Starting from the end of both words, we fill in the `dp` array based on the following conditions:\n1. If the characters at positions `i` and `j` are the same, no operation is required, so `dp[i][j] = dp[i + 1][j + 1]`.\n2. If the characters at positions `i` and `j` are different, we have three options:\n   - Replace the character at position `i` in `w1` with the character at position `j` in `w2`: `dp[i][j] = 1 + dp[i + 1][j + 1]`.\n   - Delete the character at position `i` in `w1`: `dp[i][j] = 1 + dp[i + 1][j]`.\n   - Insert the character at position `j` in `w2` after position `i` in `w1`: `dp[i][j] = 1 + dp[i][j + 1]`.\n3. We take the minimum of the above three scenarios and assign it to `dp[i][j]`. This ensures that `dp[i][j]` represents the minimum number of operations required to convert the substrings `word1[:i]` to `word2[:j]`.\n\n## Step 4: Return Result\nReason: We return `dp[0][0]`, which represents the minimum number of operations required to convert `w1` to `w2`.\n\n# Complexity\n- Time complexity: \\(O(m * n)\\), where \\(m\\) and \\(n\\) are the lengths of `w1` and `w2`, respectively. We fill the entire `dp` array once.\n- Space complexity: \\(O(m * n)\\) for the dynamic programming array `dp`, where \\(m\\) and \\(n\\) are the lengths of `w1` and `w2`, respectively.\n\n## Python Code:\n\n```python\nclass Solution:\n    def minDistance(self, w1: str, w2: str) -> int:\n        # Create a 2D array to store the minimum edit distances\n        dp = [[float("inf")] * (len(w2) + 1) for i in range(len(w1) + 1)]\n\n        # Base cases: initialize the last row and column of the dp array\n        for j in range(len(w2) + 1):\n            dp[len(w1)][j] = len(w2) - j\n        for i in range(len(w1) + 1):\n            dp[i][len(w2)] = len(w1) - i\n\n        # Fill the dp array using a bottom-up approach\n        for i in range(len(w1) - 1, -1, -1):\n            for j in range(len(w2) - 1, -1, -1):\n                # If the characters are equal, no operation needed at this position\n                if w1[i] == w2[j]:\n                    dp[i][j] = dp[i + 1][j + 1]\n                else:\n                    # Minimum edit distance is one plus the minimum of three possible operations\n                    dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1])\n\n        # The result is stored in the top-left corner of the dp array\n        return dp[0][0]\n```\n\n## C++ Code:\n\n```c++\nclass Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        // Create a 2D vector to store the minimum edit distances\n        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, INT_MAX));\n\n        // Base cases: initialize the last row and column of the dp vector\n        for (int j = 0; j <= word2.size(); j++) {\n            dp[word1.size()][j] = word2.size() - j;\n        }\n\n        for (int i = 0; i <= word1.size(); i++) {\n            dp[i][word2.size()] = word1.size() - i;\n        }\n\n        // Fill the dp vector using a bottom-up approach\n        for (int i = word1.size() - 1; i >= 0; i--) {\n            for (int j = word2.size() - 1; j >= 0; j--) {\n                // If the characters are equal, no operation needed at this position\n                if (word1[i] == word2[j]) {\n                    dp[i][j] = dp[i + 1][j + 1];\n                } else {\n                    // Minimum edit distance is one plus the minimum of three possible operations\n                    dp[i][j] = 1 + min({dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]});\n                }\n            }\n        }\n\n        // The result is stored in the top-left corner of the dp vector\n        return dp[0][0];\n    }\n};\n```\n\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n
['String', 'Dynamic Programming', 'C++', 'Python3']