Solution


  • 0
    M

    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;
    }
    

Log in to reply
 

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