a
and b
, write a method - editDistance
that returns the minimum number of operations needed to transform a
into b
. The following character operations are allowed : editDistance("sale", "sales") => 1
Operations :
1) Insert "s"
editDistance("sale", "sold") => 2
Operations :
1) Replace "a" with "o"
2) Replace "e" with "d"
editDistance("sa", "s") => 1
Operations :
1) Delete "a"
memo
of size lenA+1
x lenB+1
where lenA
and lenB
are the lengths of a
and b
. Pre-fill the first cell with 0, which indicates and empty String. Pre-fill the first row and columns with the delete and insert transformation operation distances, which will be sequentially increasing. Using this information, traverse memo
and build up your solution.
int[][] memo = new int[lenA+1][lenB+1];
int
, this will happen by default.for(int i = 1; i <= lenA; i++) memo[i][0] = i;
for(int j = 1; j <= lenB; j++) memo[0][j] = j;
a.charAt(i)
== b.charAt(j)
, no transformation is required and you can carry forward the value from memo[i-1][j-1]
;if(cA == cB){
memo[i][j] = memo[i-1][j-1];
}
if(cA == cB){
memo[i][j] = memo[i-1][j-1];
}
else {
int replaceDist = 1 + memo[i-1][j-1];
int insertDist = 1 + memo[i][j-1];
int deleteDist = 1 + memo[i-1][j];
int minDist = Math.min(replaceDist,Math.min(insertDist, deleteDist));
memo[i][j] = minDist;
}
memo
.
public int editDistance(String a, String b){ }
C
Java
Python