Edit Distance
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
Using DP, time requirement is O(mn), storage can be O(mn) or O(min(m,n)). See two solutions below.
public class Solution {
public int minDistance(String word1, String word2) {
// Start typing your Java solution below
// DO NOT write main() function
int m = word1.length(), n = word2.length();
int[][] distances = new int[m+1][n+1];
distances[0][0] = 0;
for(int i=1;i<=m;i++)
distances[i][0]=i;
for(int i=1;i<=n;i++)
distances[0][i]=i;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
distances[i][j] = distances[i-1][j-1];
else
distances[i][j] = 1+Math.min(distances[i-1][j-1],Math.min(distances[i-1][j],distances[i][j-1]));
}
}
return distances[m][n];
}
}
public class Solution {
public int minDistance(String word1, String word2) {
// Start typing your Java solution below
// DO NOT write main() function
int m = word1.length(), n = word2.length();
if(m==0) return n;
if(n==0) return m;
int[] distances = new int[n+1],old = new int[n+1];
for(int i=0;i<=n;i++)
old[i]=i;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
distances[j] = j>1?old[j-1]:(i-1);
else
distances[j] = 1+Math.min(j>1?old[j-1]:(i-1),Math.min(old[j],j>1?distances[j-1]:i));
}
for(int j=1;j<=n;j++)
old[j]=distances[j];
}
return old[n];
}
}
No comments:
Post a Comment