|
| 1 | +//Refer to neetcode's video |
| 2 | + |
| 3 | +//Memoized code |
| 4 | + |
| 5 | +classSolution { |
| 6 | +publicintminDistance(Stringword1,Stringword2) { |
| 7 | +intm =word1.length()-1; |
| 8 | +intn =word2.length()-1; |
| 9 | +int[][]dp =newint[m+2][n+2]; |
| 10 | +for (int[]d:dp) { |
| 11 | +Arrays.fill(d, -1); |
| 12 | + } |
| 13 | +returnhelper(word1,word2,m,n,dp); |
| 14 | + } |
| 15 | + |
| 16 | +publicinthelper(Stringword1,Stringword2,intm,intn,int[][]dp) { |
| 17 | +//the strings are null |
| 18 | +if (m+1==0 &&n+1==0) { |
| 19 | +return0; |
| 20 | + } |
| 21 | +//one of the strings are null |
| 22 | +if (m+1==0 ||n+1==0) { |
| 23 | +returnMath.max(m+1,n+1); |
| 24 | + } |
| 25 | +//both values at the index are equal |
| 26 | +if (dp[m][n]!=-1)returndp[m][n]; |
| 27 | +if (word1.charAt(m)==word2.charAt(n)) { |
| 28 | +dp[m][n] =helper(word1,word2,m-1,n-1,dp); |
| 29 | +returndp[m][n]; |
| 30 | + } |
| 31 | +else { |
| 32 | +//try deletion |
| 33 | +intdelete =1+helper(word1,word2,m-1,n,dp); |
| 34 | +//try insertion |
| 35 | +intinsert =1+helper(word1,word2,m,n-1,dp); |
| 36 | +//try replacing |
| 37 | +intreplace =1+helper(word1,word2,m-1,n-1,dp); |
| 38 | +//now we'll choose the minimum out of these 3 and add 1 for the operation cost |
| 39 | +dp[m][n] =Math.min(Math.min(delete,insert),replace); |
| 40 | +returndp[m][n]; |
| 41 | + } |
| 42 | + } |
| 43 | +} |