7
\$\begingroup\$

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)]   
\$\endgroup\$
0
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Your code looks alright but if I may offer a different approach that is more "pythonic".

One way to address the problem is to think of it as how many chars are in the two words combined minus the repeating chars. Say S = len(s1 + s2) and X = repeating_chars(s1, s2) then the result is S - X.

To do so I've used Counter class from python collections.

the Counter is used to count the appearances of a char in the two strings combined, you can build your own Counter with a simple line but it wont have the same properties as the Class obviously, here is how you write a counter:

def counter(string):
    return {ch: string.count(ch) for ch in set(string)}

Back to the problem, here is the code for that approach:

from collections import Counter

def deletion_distance(s1, s2):
    return sum(v % 2 for v in Counter(s1 + s2).values())

Hope it helps!

Hod

\$\endgroup\$
3
  • 1
    \$\begingroup\$ First - your function is missing a return. Second - consider deletion_distance("aaa", "") \$\endgroup\$
    – stefan
    Feb 6 '19 at 22:13
  • 1
    \$\begingroup\$ Also, by merely counting letters, you lose all ordering informations. deletion_distance('ab', 'ba') should be 2 but if you only count letters, you will never be able to find this. \$\endgroup\$ Feb 7 '19 at 9:20
  • \$\begingroup\$ Mathias is correct; the problem given is total length minus twice the length of the longest common subsequence, not the total number of characters in common. The total number of characters in common can be larger. \$\endgroup\$ Mar 9 '19 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.