Problem Statement
What is the Edit Distance problem? Explain its dynamic programming solution.
Explanation
Edit Distance, or Levenshtein Distance, measures the minimum operations (insert, delete, replace) needed to convert one string into another. The DP solution builds a matrix where dp[i][j] represents operations to convert first i chars of word1 to first j chars of word2. Recurrence: if chars equal, dp[i][j]=dp[i-1][j-1]; else dp[i][j]=1+min(insert,delete,replace). Time and space: O(m*n).
Code Solution
SolutionRead Only
int editDistance(String a,String b){
int m=a.length(),n=b.length();
int[][] dp=new int[m+1][n+1];
for(int i=0;i<=m;i++) dp[i][0]=i;
for(int j=0;j<=n;j++) dp[0][j]=j;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a.charAt(i-1)==b.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
}
}
return dp[m][n]; }Practice Sets
This question appears in the following practice sets:
