✅ REC->MEMOIZATION->TABULATION | JAVA | EXPLAINED🔥🔥🔥
1. Recursion:\n\nThe f function recursively calculates the minimum number of operations needed to convert s1 to s2 from given indices.\nThe base cases handle wh
**1. Recursion:**\n\nThe f function recursively calculates the minimum number of operations needed to convert s1 to s2 from given indices.\nThe base cases handle when either string is empty, in which case the operations required are the length of the non-empty string.\nIf the current characters in s1 and s2 match, no operation is needed, and the recursion proceeds with the remaining characters.\nOtherwise, the minimum of insert, delete, and replace operations is calculated recursively, and 1 is added to account for the operation.\n\n**2. Memoization:**\n\nA 2D dp array is used to store the calculated results for subproblems.\nThe f function checks if the result for the current indices is already stored in dp. If so, it returns the stored value.\nOtherwise, the recursive calls are made, and the result is stored in the dp array for future reference.\n\n**3. Tabulation:**\n\nA 2D dp array is initialized with the base cases: the first row and column are filled with the corresponding indices (0, 1, 2, ...) to represent the operations needed to convert an empty string to a string of that length.\nThe dp array is filled iteratively, calculating each cell\'s value based on the previous cells and the current characters in s1 and s2.\nTime Complexity:\n\n**Time Complexity:** O(2^(m+n)), where m and n are the lengths of s1 and s2, respectively. The exponential growth is due to the recursive calls exploring different combinations of insert, delete, and replace operations.\nMemoization/Tabulation: O(m * n), as the dp array stores results for all possible states (m rows and n columns), and the iterations are linear.\n\n**Space Complexity:**\n\nRecursion: O(m + n) due to the recursion stack.\nMemoization/Tabulation: O(m * n) due to the dp array.\n\n# Code\n```java []\nclass Solution {\n    // //Recurrsion\n    // public int minDistance(String s1, String s2) {\n    //     int n= s1.length();\n    //     int m= s2.length();\n    //     return f(s1, s2, n-1, m-1);\n    // }\n\n    // public int f(String s1, String s2, int ind1, int ind2){\n    //     if(ind1 < 0) return ind2+1; // base case, here we will be deleting the remaining elements to match the other string\n    //     if(ind2 < 0) return ind1+1;\n\n    //     if(s1.charAt(ind1) == s2.charAt(ind2)){  // if matched then no operation needed\n    //         return 0 + f(s1, s2, ind1-1, ind2-1);\n    //     }else{\n    //         int insert=  f(s1, s2, ind1, ind2-1); //hypostetically inserting so just imagine the it was added and stay ind1 on same posi\n    //         int delete=  f(s1, s2, ind1-1, ind2); // deleted so move ind1 - 1\n    //         int replace=  f(s1, s2, ind1-1, ind2-1); // replaced so moved voth ind by -1\n    //         return  1 + Math.min(insert, Math.min(delete, replace));\n    //     }\n    // }\n\n\n    //Memoization\n    // public int minDistance(String s1, String s2) {\n    //     int n= s1.length();\n    //     int m= s2.length();\n    //     int[][] dp= new int[n][m];\n    //     for(int[] rows : dp){\n    //         Arrays.fill(rows, -1);\n    //     }\n    //     return f(s1, s2, n-1, m-1, dp);\n    // }\n\n    // public int f(String s1, String s2, int ind1, int ind2, int[][] dp){\n    //     if(ind1 < 0) return ind2+1;\n    //     if(ind2 < 0) return ind1+1;\n\n    //     if(dp[ind1][ind2] != -1){\n    //         return dp[ind1][ind2];\n    //     }\n\n    //     if(s1.charAt(ind1) == s2.charAt(ind2)){\n    //         return dp[ind1][ind2]= 0 + f(s1, s2, ind1-1, ind2-1, dp);\n    //     }else{\n            // int insert=  f(s1, s2, ind1, ind2-1, dp);\n            // int delete=  f(s1, s2, ind1-1, ind2, dp);\n            // int replace=  f(s1, s2, ind1-1, ind2-1, dp);\n    //         return dp[ind1][ind2]= 1 + Math.min(insert, Math.min(delete, replace));\n    //     }\n    // }\n\n     //Tabulation\n    public int minDistance(String s1, String s2) {\n        int n= s1.length();\n        int m= s2.length();\n        int[][] dp= new int[n+1][m+1];\n        \n        for(int i=0; i<= m; i++){  // adding base case, and as we have done shifting of indexes, 1 index has been shifted to left side, so we are taking  dp[0][i]= i and not i+1\n            dp[0][i]= i;\n        }\n\n        for(int i=0; i<=n; i++){\n            dp[i][0]= i;\n        }\n\n        for(int i= 1; i<=n; i++){\n           for(int j=1; j<=m; j++){\n               if(s1.charAt(i-1) == s2.charAt(j-1)){\n                   dp[i][j]= 0 + dp[i-1][j-1];\n               }else{\n                int insert = dp[i][j-1];\n                int delete = dp[i-1][j];\n                int replace = dp[i-1][j-1];\n                dp[i][j] = 1 + Math.min(insert, Math.min(delete, replace));\n               }\n           }\n        }\n        return dp[n][m];\n    }\n}\n```
['Java']