TC : O(n*m)
SC : O(n+m)( recursive stack space) + O(n*m)(dp array)
class Solution {
public int editDistance(String str1, String str2) {
// Code here
int dp[][] = new int[str1.length()][str2.length()];
for(int d[] : dp) Arrays.fill(d,-1);
return minop(0,0,str1,str2,dp);
}
public int minop(int i, int j , String a,String b, int dp[][]){
//base case
if(i==a.length() && j!=b.length()) return b.length()-i;
if(j ==b.length() && i!=a.length()) return a.length()-j;
if(i ==a.length() && j ==b.length()) return 0;
if(dp[i][j]!=-1) return dp[i][j];
//if match increment both the indexes
if(a.charAt(i) == b.charAt(j)){
return dp[i][j] = minop(i+1,j+1,a,b,dp);
}
else{
//if not match we will have to perform 1 operation either remove the char at index i ( then i will go to next char in a: i+1)
// or insert char at index i, ( insert the same char which is present at j in b,) resulting in i staying at the same index
//, and j = j+1( since the inserted char at i in a matched with char at j in b)
//or replace char at i in a with the same char at j in b, hence i will go to next char in a at i+1, j will go to next char at j +1
return dp[i][j] = 1 +
Integer.min(minop(i+1,j,a,b,dp),Integer.min(minop(i+1,j+1,a,b,dp),minop(i,j+1,a,b,dp)));
}
}
}
Top comments (0)