Java || Recursion || Memoization || Easy
Memoization Code is much better than recursion, yes DP is more fast than memoization. I put this because lots of students get confused while doing memoization\n
Memoization Code is much better than recursion, yes DP is more fast than memoization. I put this because lots of students get confused while doing memoization\n To do any Dp question, follow these three steps :-\n1. Try to make solution via recursion\n2. Try to make solution via memoization\n3. then move to Dp\n```    \n    //Memoization Code\n     public int minDistance(String word1, String word2) {\n         int m = word1.length();\n         int n = word2.length();\n         int storage[][] = new int[m+1][n+1];\n         for(int i=0;i<=m;i++){\n             for(int j=0;j<=n;j++){\n             storage[i][j] = -1;\n             }\n         }\n         \n         return editMemo(word1,word2,storage);\n     }\n    \n    public int editMemo(String word1, String word2, int storage[][]){\n        int m = word1.length();\n         int n = word2.length();\n        if(storage[m][n] != -1){\n            return storage[m][n];\n        }\n        if(m==0) return storage[m][n] = n;\n        if(n==0) return storage[m][n] = m;\n         if(word1.charAt(0) == word2.charAt(0)){\n            return storage[m][n] = editMemo(word1.substring(1),word2.substring(1),storage);\n         }else{\n               //insert\n            int insert = editMemo(word1,word2.substring(1),storage);\n             //delete\n            int delete = editMemo(word1.substring(1),word2,storage);\n             //replace \n            int replace = editMemo(word1.substring(1),word2.substring(1),storage);\n              storage[m][n] = 1 + Math.min(insert,Math.min(delete,replace));\n         }\n        return storage[m][n];\n    }\n    \n```    \n    \n\t\n   It gives us TLE, because strings present in test cases can be so long\n   ```\n   // Recursion Solution\n    public int minDistance(String word1, String word2) {\n         if(word1.length() == 0){\n             return word2.length();\n         }\n         if(word2.length() == 0){\n             return word1.length();\n         }\n        \n         if(word1.charAt(0) == word2.charAt(0)){\n             return minDistance(word1.substring(1),word2.substring(1));\n        }else{\n             //insert\n             int insert = minDistance(word1,word2.substring(1));\n              //delete\n             int delete = minDistance(word1.substring(1),word2);\n              //replace \n             int replace = minDistance(word1.substring(1),word2.substring(1));\n               return 1 + Math.min(insert,Math.min(delete,replace));\n         }\n     }\n\t ```\n**If you like this, please upvote and like this**
['Recursion', 'Memoization', 'Java']