Minimum Edit Distance Between Two Words- Java Solution
Intuition\n- The problem is to find the minimum number of operations required to convert one word into another. The allowed operations are insertion, deletion, 
# Intuition\n- The problem is to find the minimum number of operations required to convert one word into another. The allowed operations are insertion, deletion, or substitution of a character. This is a classic dynamic programming problem.\n\n# Approach\n1. Initialize DP Table: Create a 2D array dp where dp[i][j] represents the minimum number of operations to convert the first i characters of word1 to the first j characters of word2.\n1. Base Cases:\n    - dp[0][j] = j for all j (converting empty string to the first j characters of word2).\n    - dp[i][0] = i for all i (converting the first i characters of word1 to an empty string).\n3. Fill DP Table: Use the following recurrence relation:\n    - If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1].\n    - Otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), which represents the minimum of the three possible operations (insert, delete, substitute).\n4. Result: The value dp[m][n] will be the answer, where m and n are the lengths of word1 and word2, respectively.\n\n# Complexity\n- Time complexity:- O(m\xD7n) where m and n are the lengths of word1 and word2. We fill a DP table of size m x n.\n\n- Space complexity:- \uD835\uDC42(\uD835\uDC5A\xD7\uD835\uDC5B) for the DP table.\n\n# Code\n```\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        int m=word1.length();\n        int n=word2.length();\n        int[][] dp=new int[m+1][n+1];\n        for(int i=0;i<=m;i++)\n        {\n            for(int j=0;j<=n;j++)\n            {\n                if(i==0) dp[i][j]=j;\n                else if(j==0) dp[i][j]=i;\n                else if(word1.charAt(i-1)==word2.charAt(j-1))\n                {\n                    dp[i][j]=dp[i-1][j-1];\n                }\n                else\n                {\n                    dp[i][j]=1+(Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1])));\n                }\n            }\n        }\n        return dp[m][n];\n    }\n}\n```\n# **Conclusion**\n- By using dynamic programming, we can efficiently solve the problem of finding the minimum number of operations required to convert one word into another. This approach ensures that we consider all possible transformations and compute the optimal solution in a structured manner.
['Java']