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. Generic Case (different lengths)
2. Same lengths
3. No change required
4. All the characters need to be changed
5. One of the string is empty
6. Both strings are empty

"""
'\n1. Generic Case (different lengths)\n2. Same lengths\n3. No change required\n4. All the characters need to be changed\n5. One of the string is empty\n6. Both strings are empty\n\n'
def min_edit_distance(str1, str2, i1=0, i2=0):
    if i1 == len(str1):
        return len(str2) - i2
    if i2 == len(str2):
        return len(str1) - i1
    if str1[i1] == str2[i2]:
        return min_edit_distance(str1, str2, i1+1, i2+1)
    return 1 + min(min_edit_distance(str1, str2, i1, i2+1), # Insert at beginning of str1
                   min_edit_distance(str1, str2, i1+1, i2), # Remove from beginning of str1
                   min_edit_distance(str1, str2, i1+1, i2+1)) # Swap first character of str1
        
def min_edit_distance2(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)

Brute force (recursion - exponential):