Learn practical skills, build real-world projects, and advance your career
Updated 3 years ago
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)
# 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):