# Solution

• Let str1 and str2 be two strings of length m and n respectively. Our aim is to convert str1 to str2 in minimum number of operations.
Operations allowed are -
i) Insert
ii) Delete
iii) Replace

Let C[m][n] is the edit distance of converting str1 of length m to str2 of length n.
C[i][j] = edit distance of converting str1[1...i] into str2[1...j].
Then, following is the recurrence relation for this problem-
C[m][n] = C[m-1][n-1], if str1[m] = str2[n] i.e., we don't have to apply any operation since str1[m] = str2[n]
Now, if str1[m] != str2[n],
then, either we can replace str1[m] by str2[n] in which case the edit distance = 1 + C[m-1][n-1]
or we can insert str2[n] in front of str1[m-1] in which case the edit distance = 1 + C[m][n-1]
or we can delete str1[m] and the edit distance of converting str1 to str2 becomes 1 + C[m-1][n].
So, C[m][n] = minimum of the three i.e.,
C[m][n] = 1 + min(C[m-1][n-1], C[m-1][n], C[m][n-1]).

The time complexity of this algorithm is O(mn)
and the space complexity is also the same i.e., O(m
n) .
But we can observe from above recurrence relation that to fill any entry C[i][j] we require only the two rows, i th row and (i-1)th row.
So the space complexity can be reduced to O(n).
The space complexity of my implementation is O(n).

``````#include <iostream>
#include <string>
using namespace std;

unsigned long long minOf(unsigned long long a, unsigned long long b, unsigned long long c) {
if(a < b && a < c)
return a;
if(b < c)
return b;
else
return c;
}

int main() {

string str1, str2;
cout<<"Enter string 1 : ";
cin>>str1;
cout<<"Enter string 2 : ";
cin>>str2;
unsigned long int m = str1.length();
unsigned long int n = str2.length();
unsigned long long *first, *second, *temp;
first = new unsigned long long[n+1];
second = new unsigned long long[n+1];
for(int i=0;i<=n;i++) {
first[i] = i;  // as the str1 is empty so edit distance = number of characters in str2
}
for(int i=1;i<=m;i++) {
second[0] = i;
for(int j=1;j<=n;j++) {
if(str1[i-1] == str2[j-1]) {
second[j] = first[j-1];   // case 1
}
else {
second[j] = 1 + minOf(first[j-1], first[j], second[j-1]);   // case 2
}
}
//swapping the pointers
temp = first;
first = second;
second = temp;
}
cout<<first[n]<<endl;
return 0;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.