Java Solution | Memoization + Tabulation | DP
Both Memoization And Tabulation solutions are given below, you can choose any.\nIf you like the approach, then UPVOTE :) please\n\nMemoization Solution:\ndist(s
Both Memoization And Tabulation solutions are given below, you can choose any.\nIf you like the approach, then UPVOTE :) please\n\nMemoization Solution:\ndist(s1 , s2 , i , j-1 , dp) => It implies insertion at end (I have not said replacing) hypothetically\ndist(s1 , s2 , i-1 , j , dp) => It implies deletion\ndist(s1 , s2 , i-1 , j-1 , dp) => It implies replacing\n```\nclass Solution {\n    public int minDistance(String w1, String w2) {\n        int l1 = w1.length();\n        int l2 = w2.length();\n        \n        int[][] dp = new int[l1][l2];\n        for(int i = 0 ; i < l1 ; i++)\n            for(int j = 0 ; j < l2 ; j++)\n                dp[i][j] = -1;\n        return dist(w1 , w2 , l1-1, l2-1 , dp);    \n    }\n    \n    public int dist(String s1, String s2 , int i , int j , int[][] dp){\n        if(i < 0)   return j+1;\n        if(j < 0) return i+1;\n        \n        if(dp[i][j] != -1)\n            return dp[i][j];\n        \n        if(s1.charAt(i) == s2.charAt(j))    return dp[i][j] = dist(s1 , s2 , i-1 , j-1 , dp);\n        \n        return dp[i][j] = 1+Math.min(dist(s1 , s2 , i , j-1 , dp) , Math.min(dist(s1 , s2 , i-1 , j , dp) , dist(s1 , s2 , i-1 , j-1 , dp)));\n    }\n}\n```\n\nTabulation Solution:\n```\nclass Solution {\n    public int minDistance(String w1, String w2) {\n        int l1 = w1.length();\n        int l2 = w2.length();\n        \n        int[][] dp = new int[l1+1][l2+1];\n        for(int i = 0 ; i <= l1 ; i++)\n            dp[i][0] = i;\n        \n        for(int j = 0 ; j <= l2 ; j++)\n            dp[0][j] = j;\n        \n        for(int i = 1 ; i <= l1 ; i++)\n            for(int j = 1 ; j <= l2 ; j++){\n                if(w1.charAt(i-1) == w2.charAt(j-1))   dp[i][j] = dp[i-1][j-1];\n        \n                else    dp[i][j] = 1 + Math.min(dp[i][j-1] , Math.min(dp[i-1][j] , dp[i-1][j-1]));\n            }\n        \n        return dp[l1][l2];\n    }\n} \n```\nHaven\'t UPVOTED yet, can do it now :)
['Dynamic Programming', 'Memoization', 'Java']