Deletion Distance between 2 strings I was solving this problem at Pramp and I have trouble figuring out the algorithm for this problem. I'll paste the problem description and how I kind of solved it. It's the correct solution.  It is similar to the edit distance algorithm and I used the same approach.  I just wanted to see what are other ways to solve this problem.


  The 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:
  
  By deleting 'e' and 'a' in "heat", and 'i' in "hit", we get the string "ht" in both cases.
  We cannot get the same string from both strings by deleting 2 letters or fewer.
  Given 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.
  
  Examples:
  input:  str1 = "dog", str2 = "frog"
  output: 3
  input:  str1 = "some", str2 = "some"
  output: 0
  input:  str1 = "some", str2 = "thing"
  output: 9
  input:  str1 = "", str2 = ""
  output: 0  


What I want to do in this solution, is to use dynamic programming in order to build a function that calculates opt(str1Len, str2Len). Notice the following:
I use dynamic programming methods to calculate opt(str1Len, str2Len), i.e. the deletion distance for the two strings, by calculating opt(i,j) for all 0 ≤ i ≤ str1Len, 0 ≤ j ≤ str2Len, and saving previous values 

  def deletion_distance(s1, s2):
    m = [[0 for j in range(len(s2) +1)] for i in range(len(s1)+1)] 
    for i in range(len(s1)+1):
      for j in range(len(s2)+1):
        if i == 0:
          m[i][j] = j
        elif j == 0:
          m[i][j] = i
        elif s1[i-1] == s2[j-1]:
          m[i][j] = m[i-1][j-1]
        else:
          m[i][j] = 1 + min(m[i-1][j], m[i][j-1])
    return m[len(s1)][len(s2)]
I was solving this problem at Pramp and I have trouble figuring out the algorithm for this problem.


On the contrary, you've done a very good job of coming up with a solution. There are ways to improve it though.

As you note, this is just the Longest Common Subsequence problem in a thin disguise.  The "deletion distance" between two strings is just the total length of the strings minus twice the length of the LCS.

That is, the LCS of dogs (4 characters) and frogs (5 characters) is ogs (3 characters), so the deletion distance is (4 + 5) - 2 * 3 = 3.

Therefore, all you need to do to solve the problem is to get the length of the LCS, so let's solve that problem.

Your solution is pretty good but the primary problem is that it takes O(mn) time and memory if the strings are of length m and n.  You can improve this.  

The first thing to notice is that if the strings have a common prefix or suffix then you can automatically eliminate it.  That is, the deletion distance for Who let the big dogs out? and Who let the little frogs out? is the same as the deletion distance for big d and little fr. It is very cheap and easy to determine if two strings have a common prefix and suffix, and you go from having an array with 25*29 elements to an array with 5*9 elements, a huge win.

The next thing to notice is: you build the entire m*n array up front, but while you are filling in the array, m[i][j] only ever looks at m[i-1][j-1] or m[i-1][j] or m[i][j-1]. Since you never look at an array line that is two away, you don't ever need more than two lines! That is, you can:


allocate and compute the first line
allocate and compute the second line given the first line
throw away the first line; we'll never use it again
allocate and compute the third line from the second line
throw away the second line
… and so on


You still do O(mn) operations, and you still allocate in total the same amount of memory, but you only have a small amount of it in memory at the same time.  If the strings are large, that's a considerable savings.