Edit Distance Recursive solution

[Syed0208]

Please change the recursive call to find the min by removing the check for same characters and make that condition as a separate one (as it is producing wrong output).

code:

if(str1[len1] == str2[len2])
            return recEditDistance(str1, str2, len1 + 1, len2 + 1);

    return 1 + min(recEditDistance(str1, str2, len1 + 1, len2 + 1),
                recEditDistance(str1, str2, len1, len2 + 1),
                recEditDistance(str1, str2, len1 + 1, len2)); 

[harshgandhi-1999]

Please you can give the example test case so that i can see the issue

[Syed0208]

String str1 = "azced"; String str2 = "abcdef"; This is the one taught by Tushar as well. For the recursive code, it gives 1 as output but the actual output is 3

[harshgandhi-1999]

my answer is coming 3 only, you must have taken base condition wrong or pass parameters wrong

include <bits/stdc++.h>

using namespace std;

int editDist(string str1, string str2, int len1, int len2) { if (str1.length() == len1) { return str2.length() - len2; } if (str2.length() == len2) { return str1.length() - len1; } if (str1[len1] == str2[len2]) return editDist(str1, str2, len1 + 1, len2 + 1);

return 1 + min(editDist(str1, str2, len1 + 1, len2 + 1),
               editDist(str1, str2, len1, len2 + 1),
               editDist(str1, str2, len1 + 1, len2));

}

int main() { string str1 = "azced"; string str2 = "abcdef";

cout << editDist(str1, str2, 0,
                 0);

return 0;

}

[Syed0208]

I was looking at java solution in https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/EditDistance.java (this is different)

[harshgandhi-1999]

that solution is somewhat different and i am not able to understand the last step he has done in return statement so i have changed the code.