Jovian
Sign In
Learn practical skills, build real-world projects, and advance your career

Minimum Edit Distance

The following interview was asked during a coding interview at Google:

Given two strings A and B, find the minimum number of steps required to convert A to B. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word:

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

Here's a visual representation (source: iDeserve)

alt

# Solve the problem here

# 1 step: To clarify the problem

# inputs (Two strings)
str1 = 'intention'
str2 ='execution'
#output (The edit distance= A single number)
output1 = 4

# function signature
def min_steps(str1, str2):
    pass

# 2 step: list out some test cases
"""
1. general case(listed above: intention, execution and few more examples )
2. no change is required ( you are given the same string)
3. all the characters need to be changed (add , remove, delete)
4. equal length (both strings have an equal lenght)
5 unequal length (both strings have an equal lenght)
6.one of the strings is empty
7. only deletion, only addition, only swap

"""

# 3-Step: Come up with a simple solution to the problem (Whenever you are in doubt, think about recursion)

""""
Recursion:
-if the first character is equal, then ignore from both
-if the fisrt chacter is not equal: 
    - either it has to be deleted
      - 1 + recursively solved after ignoring first character str1
    -or sawpped
      - 1 + recursively solved after ignoring the first character of each
    -or a character inserted before 
      - 1 + recursively solve after ignoring first character of str2  
"""
def min_edit_distance (str1, str2, i1=0, i2=0):          # i1 and i2 are pointers or index
        print(str1[i1:], str2[i2:])
        if i1 == len(str1):
            return len(str2) - i2
        elif i2 == len(str2):                   # Case where the second string is empty
            return len(str1) - i1
        elif str1[i1] == str2[i2]:              # Case where str1 = str2
            return min_steps(str1, str2, i1+1,i2+1)
        else:
            return 1 + min(min_edit_distance(str1, str2, i1+1, i2), # deleted
                           min_edit_distance(str1, str2, i1+1, i2+1), # swap
                           min_edit_distance(str1, str2, i1, i2+1)) # inserted
# Memorization
def min_edit_distance_memo(str1, str2):
    memo = {}
    def recurse(i1, i2):
        key = (i1, i2)
        if key in memo:
            return memo[key]
        elif i1 == len(str1):
            memo[key] = len(str2) - i2
        elif i2 == len(str2):
            memo[key] = len(str1) - i1
        elif str1[i1] == str2[i2]:
            memo[key] = recurse(i1+1, i2+1)
        else:
            memo[key] = 1 + min(recurse(i1, i2+1), 
                                recurse(i1+1, i2), 
                                recurse(i1+1, i2+1))
        return memo[key]
    return recurse(0, 0)
    
# Test the solution here

"""
1. general case(listed above: intention, execution and few more examples )
2. no change is required ( you are given the same string)
3. all the characters need to be changed (add , remove, delete)
4. equal length (both strings have an equal lenght)
5 unequal length (both strings have an equal lenght)
6.one of the strings is empty
7. only deletion, only addition, only swap

"""
# To test the case where one of the string is empty
min_edit_distance('int', '')
int 
3
# To test the case where the string is empty
min_edit_distance('', 'int')
int 
3
# To test the case where str1 and str2 are equals
min_edit_distance_memo('int','india')
3