Learn practical skills, build real-world projects, and advance your career
Created 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
# Input
str1 = "intention"
str2 = "execution"
# Output
output1 = 5
# Function
def min_steps(str1, str2):
pass
"""
1. General case
2. No change is required
3. All the characters need to be changed
4. Unequal length
5. One of the strings is empty
7. Only deletion, only addition, only swap
"""
"""
Recursion:
- if both characters are equal, ignore
- if one character is not equal
- it has to be deleted
- recursively solve after ignoring first character of str1
- swapped
- recursively solve after ignoring the first character of each
- inserted before
- recursively solve after ignoring the first character of str2
"""
def min_steps(str1, str2, i1=0, i2=0):
if i1 == len(str1):
return len(str2) - i2
elif i2 == len(str2):
return len(str1) - i1
elif str1[i1] == str2[i2]:
return min_steps(str1, str2, i1+1, i2+1)
else:
return 1 + min(min_steps(str1, str2, i1+1, i2), # delete
min_steps(str1, str2, i1+1, i2+1), #swap
min_steps(str1, str2, i1, i2+1)) # insert
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+1, i2),
recurse(i1+1, i2+1),
recurse(i1, i2+1))
return memo[key]
return recurse(0, 0)
# O(N) = n1 * n2# Test the solution heremin_steps("int", "")3min_steps("", "int")3