✅ EASY || 100 % BEATS-PROOF || 🌟 JAVA || 🧑‍💻 BEGINNER FRENDLY || 📝 DETAILED EXPLANATION
\n\n# \uD83D\uDCD2 PROOF\n---\n\n\n---\n\n\n# \uD83D\uDCD2 Intuition\n---\n Describe your first thoughts on how to solve this problem. \nThe problem requires tr
```\n```\n# \uD83D\uDCD2 PROOF\n---\n![image.png](https://assets.leetcode.com/users/images/0ad432b1-a057-4759-810b-6cc65f672f5a_1733192777.1053894.png)\n\n---\n```\n```\n# \uD83D\uDCD2 Intuition\n---\n<!-- Describe your first thoughts on how to solve this problem. -->\n**The problem requires transforming one string into another using three operations: insert, delete, or replace. This is a classic Dynamic Programming problem, where we aim to minimize the cost of edits. The solution involves comparing prefixes of both strings to compute the minimum operations required.**\n```\n```\n# \uD83D\uDCD2 Approach\n---\n<!-- Describe your approach to solving the problem. -->\n1. ### Define Subproblem:\n    - #### Let dp[i][j] represent the minimum operations required to transform the first i characters of word1 into the first j characters of word2.\n2. ### Recursive Relations:\n    - #### If the current characters of word1 and word2 match, no operation is needed: dp[i][j]=dp[i\u22121][j\u22121]\n    - #### Otherwise, consider the three possible operations:\n        - Insert a character into word1: dp[i][j]=1+dp[i][j\u22121]\n        - Delete a character from word1: dp[i][j]=1+dp[i\u22121][j]\n        - Replace a character in word1: dp[i][j]=1+dp[i\u22121][j\u22121]\n    - #### Take the minimum of these three.\n3. ### Base Cases:\n    - #### If one string is empty, the cost is the length of the other string (all insertions or deletions).\n    - #### dp[i][0]=i\n    - #### dp[0][j]=j\n4. ### Implementation:\n    - #### Use a 2D dp table of size (m+1)\xD7(n+1), where m and n are the lengths of word1 and word2.\n5. ### Optimization:\n    - #### Since we only need the previous row to calculate the current row, space can be optimized to O(min(m,n)).\n```\n```\n# \uD83D\uDCD2 Complexity\n---\n- ### Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n**O(m\xD7n), where m and n are the lengths of word1 and word2.**\n\n---\n- ### Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n**O(m\xD7n) for the 2D DP table or O(min(m,n)) for the optimized version.**\n```\n```\n# \uD83D\uDCD2 Code\n---\n```java []\nclass Solution {\n    private int solve(int i, int j, String s1, String s2, int dp[][]) {\n        if (i == 0 && j == 0) {\n            if (s1.charAt(i) == s2.charAt(j))\n                return 0;\n            else\n                return 1;\n        }\n        if (j == -1)\n            return i + 1;\n        if (i == -1)\n            return j + 1;\n\n        if (dp[i][j] != -1)\n            return dp[i][j];\n\n        int insert = 300000000;\n        int replace = 30000000;\n        int delete = 30000000;\n\n        if (s1.charAt(i) == s2.charAt(j)) \n            return dp[i][j] = solve(i - 1, j - 1, s1, s2, dp);\n        else {\n            insert = 1 + solve(i, j - 1, s1, s2, dp);\n            replace = 1 + solve(i - 1, j - 1, s1, s2, dp);\n            delete = 1 + solve(i - 1, j, s1, s2, dp);\n        }\n\n        return dp[i][j] = Math.min(insert, Math.min(replace, delete));\n    }\n\n    public int minDistance(String word1, String word2) {\n        int dp[][] = new int[word1.length()][word2.length()];\n\n        for (int[] I : dp)\n            Arrays.fill(I, -1);\n\n        return solve(word1.length() - 1, word2.length() - 1, word1, word2, dp);\n    }\n}\n```\n```\n```\n---\n![upvote.png](https://assets.leetcode.com/users/images/d921c426-e853-497e-8030-df3880e9d628_1733192794.393367.png)\n\n---\n```\n```
['Java']