72. Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Lets start. How will be approach a optimization problem with overlapping subproblems ? Dynamic programming. How do we know its DP. Question says it needs minimum number of operations and for checking overlapping subproblems, lets do some of the operations manually.

Input: word1 = "horse", word2 = "ros"
We have 3 operations available. Insert (to add a character to word1), delete (to remove a character from word 1) and replace (to replace a character in word1 with word2 character.
So lets think recursively and do top down approach.
Start with last letter of word1 and word2.
If these matches, we can simply move on to next characters "hors" and "ro". This simply means deleting characters from both words without adding any operations.
But if these don't we can do 3 operations:
1. insert a character in word1 which is same as the character in word2.
2. delete a character in word1 and compare the rest with word2.
3. replacing the character in word1 with the character in word2.

If we see in word1, last character is ‘e’ and in word2, it is ‘s’. Since these don’t match, we have to choose either of the 3 operations.

1. insert => “horses”, “ros”. Since we will only insert characters which make last character of both words equal and then on next step, we can move one character left from each word. So word1 will become “horse” and word2 “ro”. You see, insertion on word1 act as deletion on act2.
2. delete => we will delete the last character in word1. Now word1 will be “hors” and word2 “ros”. It is just deletion of last character from word1.
3. replacing => we will replace last character of word1 with last character of word2. So it will become “horss” ,”ros” and on next comparison, since last characters are equal, we will move one character left from both words. word1 will become “hors” and word2 “ro”. So replacing acts as deletion in both the words.

So we can see if we do:

Operation1 (insertion), word1=“horse”, word2=”ro”

Operation2(deletion), word1=“hors”, word2=”ros”

Operation3(replacing), word1=”hors”, word2=”ro”

So we have “hors” and “ro” common in all the operations, which is an overlapping subproblem and we can solve it using DP ❤.

Deletion means the length of the strings will be one less than it was.

Lets see the recursive code for it. Before that, lets just discuss the base case for recursion as we know the other cases of when character matches and when it doesn’t.

So since we are moving left and deleting characters at each step, one way or the other, strings will keep on getting small unless one becomes null or empty string. So to convert an empty string to and word, what can we do.

Ex-> str1 = “”, str2 = “hello”

We can simply add 5 characters to str1 to make str2 or delete 5 characters from str2. Here cost is same for both. So we are adding length of the string which is not null. Now lets code.

# Operations allowed
#     Insert a character
#     Delete a character
#     Replace a character
a = "angha"
b = "antman"
def edit(i, j):
    if i <= 0 or j <= 0:
        return max(i, j)  # which ever has characters, other null string will add those many characters
    if a[i] == b[j]: # if last characters are same, we move left to the next set of characters on both words
        return edit(i-1, j-1)
    else:
        return 1+min(edit(i, j-1), edit(i-1, j-1), edit(i-1, j))
            #       inserting      replace         deleting

time complexity -> O(3^n)

Since it is an otimization problem with overlapping subproblems, lets see the DP code.

# Operations allowed
a = "sunday"
b = "saturday"
dp = [[0 for _ in range(len(b)+1)] for _ in range(len(a)+1)]
for i in range(0, len(a)+1):
    for j in range(0, len(b)+1):
        if i == 0: # if a is null, then we will do len(b) that is j number of insertions
            dp[i][j] = j
        elif j == 0: # if bis null, then we will do len(a) that is inumber of insertions
            dp[i][j] = i
elif a[i-1] == b[j-1]: # If last characters are equal, then take the last diagonal value as i
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
print(dp[i][j])

This is the DP code. It is same as recursion but here we are storing the values so we have to start from the bottom to top. We start with i, j as 0, 0. We are also taking 0 here as we want to take into account what happens when one string is null or empty.

Thanks.