Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
b) Delete a character
c) Replace a character
Solution:
We can use dynamic programming storing in a matrix how many steps are needed to get from word1.substring(0,i) to word2.substring(0,j). Then the element i,j can be calculated as follows:
M(i,j) = min( M(i-1,j) +1, M(i,j-1) +1, M(i-1,j-1)+ C),
where C= \begin{cases} 0 & \text{if word1[i]==word2[j]} \\ 1 & \text{in other case}\end{cases}.
public class Solution {
public int minDistance(String word1, String word2) {
if(word1.length()==0)
return word2.length();
if(word2.length()==0)
return word1.length();
int[][] steps = new int[word1.length()+1][word2.length()+1];
for(int i=0; i<=word1.length(); i++)
steps[i][0]=i;
for(int j=0; j<=word2.length(); j++)
steps[0][j]=j;
for(int j=1; j<=word2.length(); j++)
{
for(int i=1; i<=word1.length(); i++)
{
steps[i][j] = steps[i-1][j]<steps[i][j-1] ? steps[i-1][j] +1 : steps[i][j-1]+1; //Adding a letter
if(word1.charAt(i-1) == word2.charAt(j-1))
steps[i][j] = steps[i][j] > steps[i-1][j-1] ? steps[i-1][j-1] : steps[i][j];
else
steps[i][j] = steps[i][j] > steps[i-1][j-1]+1 ? steps[i-1][j-1]+1 : steps[i][j];
}
}
return steps[word1.length()][word2.length()];
}
}
No comments :
Post a Comment