minimum deletion

 1from functools import lru_cache
 2
 3
 4@lru_cache(None)
 5def 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
13print(dist("dog", "frog"))

 1"""
 2DP, with deletions until min distance is found
 3Time: O(M*N) 
 4Space: O(mn)
 5O(1)
 6
 7   '' H E A T
 8''  0 1 2 3 4
 9H   1 0 1 0 0
10I   2 0 0 0 0 
11T   3 0 0 0 
12
13"""
14
15def deletion_distance(a, b):
16  def dp(a, b):
17    if (a, b) in mem:
18      return mem[(a, b)]
19    if a == '' or b == '':
20      mem[(a, b)] = len(a) or len(b)
21      return mem[(a, b)]
22    if a[-1] == b[-1]:
23      mem[(a, b)] = dp(a[:-1], b[:-1])
24      return mem[(a, b)]
25    mem[(a, b)] = min(dp(a, b[:-1]), dp(a[:-1], b)) + 1
26    return mem[(a, b)]
27  mem = {}  
28  return dp(a, b)
29
30
31
32
33"""
34Deletion Distance
35
36The deletion distance of two strings is the minimum number of characters you need to delete in the two strings in order to get the same string. For instance, the deletion distance between "heat" and "hit" is 3:
37By deleting 'e' and 'a' in "heat", and 'i' in "hit", we get the string "ht" in both cases.
38We cannot get the same string from both strings by deleting 2 letters or fewer.
39
40Given the strings str1 and str2, write an efficient function deletionDistance that returns the deletion distance between them. Explain how your function works, and analyze its time and space complexities.
41
42STR1 = HEAT
43STR2 = HIT
44ANS - 3
45
46   '' H E A T
47''  0 1 2 3 4
48H   1 0 1 2 3
49I   2 1 2 3 4
50T   3 2 3 4 3
51
52base case:
53empty string - don't delete - 0
54
55if chars match:
56dp[i][j] = dp[i-1][j-1]
57
58if chars mismatch:
59dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
60"""
61
62
63def deletion_distance(str1, str2):
64    dp = [[0 for _ in range(len(str2)+1)] for _ in range(len(str1)+1)]
65
66    for i in range(len(str1)+1):
67        dp[i][0] = i
68
69    for j in range(len(str2)+1):
70        dp[0][j] = j
71
72    for i in range(1, len(str1)+1):
73        for j in range(1, len(str2)+1):
74            if (str1[i-1] == str2[j-1]):
75                dp[i][j] = dp[i-1][j-1]
76            else:
77                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
78
79    return dp[len(str1)][len(str2)]