-3
\$\begingroup\$

The edit distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other.

This task is simply to write code that determines if two strings have edit distance at most 3 from each other. The twist is that your code must run in linear time. That is if the sum of the lengths of the two strings is n then your code should run in O(n) time.

Example of strings with edit distance 2.

elephant elepanto
elephant elephapntv
elephant elephapntt
elephant lephapnt
elephant blemphant
elephant lmphant
elephant velepphant

Example of strings with edit distance 3.

   elephant eletlapt
   elephant eletpaet
   elephant hephtant
   elephant leehanp
   elephant eelhethant

Examples where the edit distance is more than 3. The last number in each row is the edit distance.

elephant leowan 4
elephant leowanb 4
elephant mleowanb 4
elephant leowanb 4
elephant leolanb 4
elephant lgeolanb 5
elephant lgeodanb 5
elephant lgeodawb 6
elephant mgeodawb 6
elephant mgeodawb 6
elephant mgeodawm 6
elephant mygeodawm 7
elephant myeodawm 6
elephant myeodapwm 7
elephant myeoapwm 7
elephant myoapwm 8

You can assume the input strings have only lower case ASCII letters (a-z).

Your code should output something Truthy if the edit distance is at most 3 and Falsey otherwise.

If you are not sure if your code is linear time, try timing it with pairs of strings of increasing length where the first is all 0s and the second string is two shorter with one of the 0s changed to a 1. These all have edit distance 3. This is not a good test of correctness of course but a quadratic time solution will timeout for strings of length 100,000 or more where a linear time solution should still be fast.

(This question is based on this older one)

\$\endgroup\$
18
  • 3
    \$\begingroup\$ Why? Does changing the edit distance from 3 to 2 make a big difference with the older question? (Also it seems that the older question was also asked by you) \$\endgroup\$
    – wasif
    Aug 29 at 17:22
  • 3
    \$\begingroup\$ I think you are lacking new challenge ideas. Simple idea:figure out the edit distance of two strings \$\endgroup\$
    – wasif
    Aug 29 at 17:28
  • 3
    \$\begingroup\$ @EliteDaMyth The edit distance is normally computed via dynamic programming. See e.g. rosettacode.org/wiki/Levenshtein_distance#Python . This takes quadratic time. For fixed distances it is however possible to compute it in linear time. A general algorithm to do this is via a variant of the dynamic programming algorithm . However for specific small but fixed distance you can do it with shorter code with some thought and tricks. Distance 1 is really easy, 2 a little trickier and 3 a little more tricky again. They really are different questions. \$\endgroup\$
    – Anush
    Aug 29 at 17:55
  • 2
    \$\begingroup\$ @wasif "figure out the edit distance of two strings " is a very different question and I think has been asked here previously. \$\endgroup\$
    – donald
    Aug 29 at 17:59
  • 1
    \$\begingroup\$ I think Wheat Wizard's answer for distance 2 is easily modifiable to any constant edit distance, and I doubt any other methods are viable for distance higher than 2. \$\endgroup\$
    – Bubbler
    Aug 30 at 0:10
2
+50
\$\begingroup\$

Haskell, 93 90 bytes

x%y=[0,0,0]>=x#y
u@(a:b)#v@(c:d)|a==c=b#d|k<-zipWith(+)=0:k(d#u)(k(b#v)$b#d)
a#b=a++b>>[0]

Try it online!

This is taken from this previous answer of mine with basically no modification.

How it works:

We start by looking at a naive version of edit distance:

lDistance :: ( Eq a ) => [a] -> [a] -> Int
lDistance [] t = length t   -- If s is empty the distance is the number of characters in t
lDistance s [] = length s   -- If t is empty the distance is the number of characters in s
lDistance (a:s') (b:t') =
  if
    a == b
  then
    lDistance s' t'         -- If the first characters are the same they can be ignored
  else
    1 + minimum             -- Otherwise try all three possible actions and select the best one
      [ lDistance (a:s') t' -- Character is inserted (b inserted)
      , lDistance s' (b:t') -- Character is deleted  (a deleted)
      , lDistance s' t'     -- Character is replaced (a replaced with b)
      ]

(I wrote this program for Wikipedia here)

This is pretty bad because every time it finds a discrepancy between the two strings it branches into 3 options (insert, delete or replace) so in the worst case it will have the time complexity of \$O(3^n)\$.

The thing to notice though is that whenever we branch we increase the total distance by 1. So if we are on a particular search path that has already branched 3 times and we would branch another time. So we can just stop there and say return False for this branch since it can never find the result.

Now there is a hard limit on the number of branches that can occur, \$3^3 = 27\$, so our computation is \$O(n)\$.

In general this strategy has a complexity of \$O(3^mn)\$ where \$m\$ is the limiting distance.

\$\endgroup\$
1
  • \$\begingroup\$ This is a very nice answer. \$\endgroup\$
    – Anush
    Sep 2 at 10:39
2
\$\begingroup\$

Prolog (SWI), 120 bytes

_+[]+[].
N+[A|B]+[A|C]:-!,N+B+C.
N+[_|B]+C:-N>0,N-1+B+C.
N+B+[_|C]:-N>0,N-1+B+C.
N+[_|B]+[_|C]:-N>0,N-1+B+C.
B*C:-3+B+C.

Try it online!

This is the same basic algorithm as my Haskell answer, but it implements it using Prolog's built in search.

We have to add a cut on the second case

N+[A|B]+[A|C]:-!,N+B+C.

If we don't the will try to branch even when the first two characters are the same. This will cause exponential branching with respect to the length of the string.

The cut here ensures that if the first two characters are the same we don't backtrack.

The Haskell answer doesn't have this issue because Haskell will eagerly follow the first path of execution.

\$\endgroup\$
1
  • \$\begingroup\$ This reads like an advert for Haskell :) \$\endgroup\$
    – Anush
    Sep 9 at 9:13
2
\$\begingroup\$

Prolog (SWI), 109 bytes

_+[]+[].
N+[A|B]+[A|C]:-!,N+B+C.
\N+B+C:-B=[_|X],N+X+C;C=[_|Y],N+B+Y;B=[_|X],C=[_|Y],N+X+Y.
B*C:- \ \ \a+B+C.

Try it online!

This is a golf of Wheat Wizard's answer. The key modification I made was that instead of using Prolog's built in numbers and arithmetic to keep track of the the current edit distance, I instead used nested compound terms, built using the unary operator \. Thus instead of having to check if N is greater than zero and then use subtraction, I can roll both of those steps into a single pattern match by matching the current remaining edit distance to \N. This left me with the following program (111 bytes):

_+[]+[].
N+[A|B]+[A|C]:-!,N+B+C.
\N+[_|B]+C:-N+B+C.
\N+B+[_|C]:-N+B+C.
\N+[_|B]+[_|C]:-N+B+C.
B*C:- \ \ \a+B+C.

I managed to save a couple more bytes by merging the latter three rules for the + predicate into a single rule, as described here.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for sneaking under the wire! \$\endgroup\$
    – Anush
    Sep 10 at 20:18

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