minimum deletion

Go Back home

This is a dynamic programming question, very similar to levenshtein distance. Given two strings, e.g frog and dog, determine how many characters need to be deleted for the words to match.

 1 from functools import lru_cache
 2 
 3 
 4 @lru_cache(None)
 5 def dist(a, b):
 6     if a == "" or b == "":
 7         return len(b) or len(a)
 8     if a[-1] == b[-1]:
 9         return dist(a[:-1], b[:-1])
10     return min(dist(a[:-1], b), dist(a, b[:-1])) + 1
11 
12 
13 print(dist("dog", "frog"))

See also:

levenshtein distance