🧐Look at once 💻 🔥Solutions in Java 📝, Python 🐍, and C++ 🖥️ with Video Explanation 🎥
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve this problem, we can use dynamic programming. We will create a 2D array to sto
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve this problem, we can use dynamic programming. We will create a 2D array to store the minimum number of operations required to convert a substring of word1 to a substring of word2.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet dp[i][j] be the minimum number of operations required to convert the first i characters of word1 to the first j characters of word2. We will fill up this 2D array from top to bottom and from left to right.\n\nIf `word1[i-1] == word2[j-1]`, then no operation is required to convert `word1[0:i-1]` to `word2[0:j-1]`. Therefore, `dp[i][j] = dp[i-1][j-1]`.\n\nIf `word1[i-1] != word2[j-1]`, then we have three options:\n\n1. Replace: Replace the i-th character of word1 with the j-th character of word2. `dp[i][j] = dp[i-1][j-1] + 1`.\n\n2. Delete: Delete the i-th character of word1.` dp[i][j] = dp[i-1][j] + 1`.\n\n3. Insert: Insert the j-th character of word2 into word1. `dp[i][j] = dp[i][j-1] + 1`.\n\nThe final answer will be stored in `dp[word1.length()][word2.length()]`.\n\n# Video reference\n<iframe width="560" height="315" src="https://www.youtube.com/embed/ZkgBinDx9Kg" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>\n\n![image.png](https://assets.leetcode.com/users/images/2b37d2cc-3ca9-4b0c-866d-48abc59d8fa5_1677216789.1769023.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A\n```\n\n\n# Complexity\n- Time complexity:\nThe time complexity of the dynamic programming solution is $$O(mn)$$, where m and n are the lengths of word1 and word2, respectively. This is because we fill up a 2D array of size (m+1) x (n+1) using nested loops.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\nThe space complexity of the dynamic programming solution is $$O(mn)$$, where m and n are the lengths of word1 and word2, respectively. This is because we use a 2D array of size (m+1) x (n+1) to store the minimum number of operations required to convert substrings of word1 to substrings of word2.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        int[][] dp = new int[word1.length()+1][word2.length()+1];\n        \n        for (int i = 0; i <= word1.length(); i++) {\n            dp[i][0] = i;\n        }\n        \n        for (int j = 0; j <= word2.length(); j++) {\n            dp[0][j] = j;\n        }\n        \n        for (int i = 1; i <= word1.length(); i++) {\n            for (int j = 1; j <= word2.length(); j++) {\n                if (word1.charAt(i-1) == word2.charAt(j-1)) {\n                    dp[i][j] = dp[i-1][j-1];\n                } else {\n                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;\n                }\n            }\n        }\n        \n        return dp[word1.length()][word2.length()];\n    }\n}\n\n```\n```javascript []\nvar minDistance = function(word1, word2) {\n    const m = word1.length;\n    const n = word2.length;\n    const dp = new Array(m+1).fill(null).map(() => new Array(n+1).fill(null));\n    \n    for (let i = 0; i <= m; i++) {\n        dp[i][0] = i;\n    }\n    \n    for (let j = 0; j <= n; j++) {\n        dp[0][j] = j;\n    }\n    \n    for (let i = 1; i <= m; i++) {\n        for (let 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] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1;\n            }\n        }\n    }\n    \n    return dp[m][n];\n};\n\n```\n```python []\nclass Solution:\n    def minDistance(self, word1: str, word2: str) -> int:\n        m, n = len(word1), len(word2)\n        dp = [[0] * (n+1) for _ in range(m+1)]\n        \n        for i in range(m+1):\n            dp[i][0] = i\n        \n        for j in range(n+1):\n            dp[0][j] = j\n        \n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                if word1[i-1] == word2[j-1]:\n                    dp[i][j] = dp[i-1][j-1]\n                else:\n                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1\n        \n        return dp[m][n]\n\n```\n```C++ []\nclass Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        int m = word1.length();\n        int n = word2.length();\n        vector<vector<int>> dp(m+1, vector<int>(n+1));\n        \n        for (int i = 0; i <= m; i++) {\n            dp[i][0] = i;\n        }\n        \n        for (int j = 0; j <= n; j++) {\n            dp[0][j] = j;\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] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;\n                }\n            }\n        }\n        \n        return dp[m][n];\n    }\n};\n`````\n\n\n\n\n\n
['Dynamic Programming', 'Python', 'C++', 'Java', 'JavaScript']