3 Best Approaches. Recursion -> Memorization -> Tabulation
Please upvote if you like these solutions\n\n# Approach\nRecursive Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time complexity
# Please upvote if you like these solutions\n\n# Approach\n**Recursive Approach**\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity : O(3^n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity : O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n class Solution {\n     public int minDistance(String word1, String word2) {\n         int n = word1.length();\n         int m = word2.length();\n\n         return minDistanceRec(word1, word2, n, m);\n     }\n\n     public int minDistanceRec(String word1,  String word2, int n, int m) {\n         if(n == 0 || m == 0){\n             return n == 0 ? m : n;\n         }\n\n         if(word1.charAt(n - 1) == word2.charAt(m - 1)){\n             return minDistanceRec(word1, word2, n - 1, m - 1);\n         }\n         else{\n             int replace = minDistanceRec(word1, word2, n - 1, m - 1);\n             int delete = minDistanceRec(word1, word2, n - 1, m);\n             int insert = minDistanceRec(word1, word2, n, m - 1);\n             return Math.min(replace, Math.min(delete, insert)) + 1;\n         }\n     }\n }\n\n```\n\n\n---\n\n\n# Approach\n**Memorization 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\n```\n class Solution {\n     public int minDistance(String word1, String word2) {\n         int n = word1.length();\n         int m = word2.length();\n\n         int [][] memo = new int [n + 1][m + 1];\n         for(int [] d : memo)\n             Arrays.fill(d, -1);\n\n         return minDistanceMemo(word1, word2, n, m, memo);\n     }\n\n     public int minDistanceMemo(String word1,  String word2, int n, int m, int [][] memo) {\n         if(n == 0 || m == 0){\n             return memo[n][m] = n == 0 ? m : n;\n         }\n\n         if(memo[n][m] != -1)\n             return memo[n][m];\n\n         if(word1.charAt(n - 1) == word2.charAt(m - 1)){\n             memo[n][m] = minDistanceMemo(word1, word2, n - 1, m - 1, memo);\n         }\n         else{\n             int replace = minDistanceMemo(word1, word2, n - 1, m - 1, memo);\n             int delete = minDistanceMemo(word1, word2, n - 1, m, memo);\n             int insert = minDistanceMemo(word1, word2, n, m - 1, memo);\n             memo[n][m] = Math.min(replace, Math.min(delete, insert)) + 1;\n         }\n         return memo[n][m];\n     }\n }\n\n```\n\n\n---\n\n\n# Approach\n**Tabulation 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\n```\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        int n = word1.length();\n        int m = word2.length();\n\n        int [][] dp = new int [n + 1][m + 1];\n        for(int [] d : dp)\n            Arrays.fill(d, -1);\n\n        return minDistanceTab(word1, word2, n, m, dp);\n    }\n\n    public int minDistanceTab(String word1,  String word2, int N, int M, int [][] dp) {\n        for(int n = 0; n <= N; n++){\n            for(int m = 0; m <= M; m++){\n                if(n == 0 || m == 0){\n                    dp[n][m] = n == 0 ? m : n;\n                    continue;\n                }\n\n                if(word1.charAt(n - 1) == word2.charAt(m - 1)){\n                    dp[n][m] = dp[n - 1][m - 1];\n                }\n                else{\n                    int replace = dp[n - 1][m - 1];;\n                    int delete = dp[n - 1][m];;\n                    int insert = dp[n][m - 1];;\n                    dp[n][m] = Math.min(replace, Math.min(delete, insert)) + 1;\n                }\n            }\n        }\n        return dp[N][M];\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']