Edit Distance

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
150 upvotes
Asked in companies
HCL TechnologiesGoogleInfosys

Problem statement

You are given two strings 'S' and 'T' of lengths 'N' and 'M' respectively. Find the "Edit Distance" between the strings.

Edit Distance of two strings is the minimum number of steps required to make one string equal to the other. In order to do so, you can perform the following three operations:

1. Delete a character
2. Replace a character with another one
3. Insert a character
Note: 
Strings don't contain spaces in between.
Detailed explanation ( Input/output format, Notes, Images )
 Input format: 
The first line of input contains the string 'S' of length 'N'.

The second line of the input contains the String 'T' of length 'M'.
Output format: 
The only line of output prints the minimum "Edit Distance" between the strings.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints: 
0 <= N <= 10 ^ 3
0 <= M <= 10 ^ 3

Time Limit : 1sec
Sample Input 1 :
abc
dc
Sample Output 1 :
2
 Explanation For Sample Input 1 :
In 2 operations we can make the string T to look like string S. First, insert the character 'a' to string T, which makes it "adc".

And secondly, replace the character 'd' of the string T with 'b' from the string S. This would make string T to "abc" which is also the string S. Hence, the minimum distance.
Sample Input 2 :
whgtdwhgtdg
aswcfg
Sample Output 2 :
9
Hint

Try to think of a recursive approach and formulate the recurrence relation. Try performing the operations as required.

Approaches (3)
Recursive Approach
  • We will write a recursive approach.
  • The base case would be if the length of the first string is 0 then we need to add all the characters of the second string to the first string hence return the length of the second string. Similarly, if the length of the second string is 0 return length of the first string.
  • Now the recurrence relation is as follows:
    • If the last characters of two strings are not the same, try all operations and it will cost 1. Here i is initially the last index of s1 and j is initially the last index of s2 and f(i, j) is the edit distance of str1(0, i) to str2(0, j). str(i, j) denotes the substring formed by taking the characters at index i through index j.
    • f(i, j) = 1 + min(f(i - 1, j), f(i, j - 1), f(i - 1, j - 1)) 
    • Here the three recursive calls are for the insert, remove and replace respectively and s1, s2 will be parameters of all function calls. If the last characters of two strings are the same (s1[i] == s2[j]) then the relationship would be:
      • f(i, j) = f(i - 1, j - 1)
Time Complexity

O(3 ^ (N * M)), Where N is the size of the first string and M is the size of the second string.

 

Since we are making 3 recursive calls each time, therefore the time complexity is O(3 ^ (N * M)).

Space Complexity

O(N + M), Where N is the size of the first string and M is the size of the second string.

Since we are making recursive calls that require the recursion stack. Therefore the space complexity is O(N + M).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Edit Distance
Full screen
Console