Beginner Friendly Step by Step Elaboration With Video Solution || Java
Intuition\nThe solution below is self explanatory. \nIf you understand Bangla, you can see this video for step by step clear explanation:\n\nhttps://youtu.be/lW
# Intuition\nThe solution below is self explanatory. \nIf you understand **Bangla**, you can see this video for step by step clear explanation:\n\nhttps://youtu.be/lWocPDgqFIo\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nRecursion With Memorization. Bottom Up Approach.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(M*N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(M*N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code [Java]\n```\nclass Solution {\n    Integer memo[][];\n    int w1Len, w2Len;\n    public int minDistance(String word1, String word2) {\n        memo = new Integer[word1.length() + 1][word2.length() + 1];\n        w1Len = word1.length();\n        w2Len = word2.length();\n        return minDistanceRecur(word1, word2, 0, 0);\n    }\n\n    int minDistanceRecur(String word1, String word2, int word1Index, int word2Index) {\n        if (word1Index == w1Len) {\n            // return how many remaining for word2\n            return w2Len-word2Index;\n        }\n        if (word2Index == w2Len) {\n            // return how many remaining for word1\n            return w1Len-word1Index;\n        }\n        if (memo[word1Index][word2Index] != null) {\n            return memo[word1Index][word2Index];\n        }\n        int minEditDistance = 0;\n        if (word1.charAt(word1Index) == word2.charAt(word2Index)) {\n            minEditDistance = minDistanceRecur(word1, word2, word1Index + 1, word2Index + 1);\n        }\n        else {\n            // insert in word1 or, delete from word1\n            int insertOperation = minDistanceRecur(word1, word2, word1Index + 1, word2Index);\n            // delete from word2 or, insert in word2\n            int deleteOperation = minDistanceRecur(word1, word2, word1Index, word2Index+1);\n            // replace so, the i\'th index of both word1 and word2 becomes equal. Now we move to i+1 th index for both.\n            int replaceOperation = minDistanceRecur(word1, word2, word1Index + 1, word2Index + 1);\n            minEditDistance = Math.min(insertOperation, Math.min(deleteOperation, replaceOperation)) + 1;\n        }\n        memo[word1Index][word2Index] = minEditDistance;\n        return minEditDistance;\n    }\n}\n```\n\n![3549-pepepopcorn.png](https://assets.leetcode.com/users/images/3ec73dd1-878d-4bc2-bf53-1096d00472ab_1677485929.702025.png)\n
['Java']