|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
| 3 | +importjava.util.Arrays; |
| 4 | + |
3 | 5 | publicclass_72 { |
4 | 6 |
|
5 | 7 | publicstaticclassSolution1 { |
@@ -35,4 +37,45 @@ public int minDistance(String word1, String word2) { |
35 | 37 | returntable[m][n]; |
36 | 38 | } |
37 | 39 | } |
| 40 | +publicstaticclassSolution2{ |
| 41 | +publicintminDistance(Stringword1,Stringword2) { |
| 42 | +// using levenshtein Distance to find minimum transformation operations required from word 1 to word 2 |
| 43 | +int[][]dp =newint[word1.length()][word2.length()]; |
| 44 | +// fill the dp array with -1 value |
| 45 | +for(int []rows :dp){ |
| 46 | +Arrays.fill(rows, -1); |
| 47 | + } |
| 48 | +returnlevenshteinDistance(word1,word1.length()-1 ,word2,word2.length()-1,dp); |
| 49 | + } |
| 50 | +privateintlevenshteinDistance(Strings1,ints1Index,Strings2,ints2Index,int[][]dp){ |
| 51 | + |
| 52 | +if(s1Index <0){// when s1 is "" perform all insertions to get s1 to s2 |
| 53 | +returns2Index +1; |
| 54 | + } |
| 55 | +elseif(s2Index <0) {// when s2 is "" perform all deletions from s1 |
| 56 | +returns1Index +1; |
| 57 | + } |
| 58 | + |
| 59 | +// base condition when dp array is filled, return the distance |
| 60 | +if(dp[s1Index][s2Index] != -1) |
| 61 | +returndp[s1Index][s2Index]; |
| 62 | + |
| 63 | +if(s1.charAt(s1Index) ==s2.charAt(s2Index)){ |
| 64 | +// Characters match, no edit distance to be calculated |
| 65 | +dp[s1Index][s2Index] =levenshteinDistance(s1,s1Index -1,s2,s2Index -1,dp); |
| 66 | + } |
| 67 | +else{ |
| 68 | +// When there is a character mismatch, perform operations |
| 69 | + |
| 70 | +// Insertion |
| 71 | +intinsertValue =levenshteinDistance(s1,s1Index,s2,s2Index -1,dp); |
| 72 | +intdeleteValue =levenshteinDistance(s1,s1Index -1,s2,s2Index,dp); |
| 73 | +intsubstituteValue =levenshteinDistance(s1,s1Index -1,s2,s2Index -1,dp); |
| 74 | + |
| 75 | +/* Now we need to take the minimum of the 3 operations to find the edit distance and add 1 to the min cost action denoting that an action is performed */ |
| 76 | +dp[s1Index][s2Index] =1 +Math.min(insertValue,Math.min(deleteValue,substituteValue)); |
| 77 | + } |
| 78 | +returndp[s1Index][s2Index]; |
| 79 | + } |
| 80 | + } |
38 | 81 | } |