15
\$\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 exactly 2 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

Examples where the edit distance is not 2. The last number in each row is the edit distance.

elephant elephant 0
elephant lephant 1
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 2 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 one shorter with one of the 0s changed to a 1. These all have edit distance 2. 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.

\$\endgroup\$
8
  • \$\begingroup\$ Given that the word size is \$W\$, would an \$O(NW)\$ solution be allowed? \$\endgroup\$ Apr 2 '20 at 20:49
  • \$\begingroup\$ @dingledooper I don’t fully understand what you mean but I suspect the answer is yes. Normally if you are to be very fussy you regard word level operations as constant time. But I don’t want to get stuck in these details here. \$\endgroup\$
    – user9207
    Apr 2 '20 at 20:51
  • 7
    \$\begingroup\$ Uh, Anush, could you look at the list of your newest questions? I see far too many patterns there \$\endgroup\$ Apr 3 '20 at 2:38
  • 8
    \$\begingroup\$ @mypronounismonicareinstate The average edit distance between Anush's challenge titles has gone down lately :P \$\endgroup\$
    – xnor
    Apr 3 '20 at 3:56
  • 1
    \$\begingroup\$ I am very glad to provide a service to fill in the terrible gap in edit distance questions which codegolf.se has had. When there are as many edit distance questions as quine questions my job will be done. \$\endgroup\$
    – user9207
    Apr 3 '20 at 10:05
7
\$\begingroup\$

Retina 0.8.2, 76 58 bytes

^(.*)(.*¶)\1
$2
(.*)(¶.*)\1$
$2
^.?¶.?$

^.?(.*).?¶.?\1.?$

Try it online! Takes the two strings on separate lines, but link includes test suite which takes space-separated strings instead, so that I can easily use the test cases. Explanation:

^(.*)(.*¶)\1
$2

Delete the common prefix.

(.*)(¶.*)\1$
$2

Delete the common suffix.

^.?¶.?$

Ignore an edit distance of less than two.

^.?(.*).?¶.?\1.?$

Check that only the first and last characters have been edited, so that the edit distance cannot be greater than two in this case.

From a code golf point of view this can be done in 51 bytes but then the regex becomes unbearably slow to execute for longer strings:

^(?!(.*).?(.*)¶\1.?\2$)(.*).?(.*).?(.*)¶\3.?\4.?\5$

Try it online! Takes the two strings on separate lines, but link includes test suite which takes space-separated strings instead, so that I can easily use the test cases. Explanation:

^

Match the whole input.

(?!(.*).?(.*)¶\1.?\2$)

Don't match strings with an edit distance less than two.

(.*).?(.*).?(.*)¶\3.?\4.?\5$

Match strings with an edit distance less than three.

\$\endgroup\$
9
  • \$\begingroup\$ This looks great but I am not sure what you have done. Take the strings abab and babz. They have no common prefix or suffix. What does your code do next? \$\endgroup\$
    – user9207
    Apr 2 '20 at 21:23
  • 1
    \$\begingroup\$ @Anush It checks that the middles of the two strings are the same, but at least one of the strings must have its first character skipped and at least one of the strings must have its last character skipped. \$\endgroup\$
    – Neil
    Apr 2 '20 at 21:44
  • \$\begingroup\$ @Anush Actually I've tweaked the code slightly now so that it simply tests all permutations of removing leading and trailing characters from both strings to see whether the remainder matches. As this now matches any strings with an edit distance of less than three I've also had to tweak my rejection to include all edits with a distance of less than two. \$\endgroup\$
    – Neil
    Apr 2 '20 at 21:51
  • \$\begingroup\$ It's a very nice and simple solution to what could have been a hard question. It also runs fast! \$\endgroup\$
    – user9207
    Apr 3 '20 at 10:07
  • 1
    \$\begingroup\$ @Anush Actually not quite as fast as it should... a one byte golf I made earlier makes the suffix removal really slow, so I've reverted that change. But if it's slow you want, I've got a 51 byte solution ;-) \$\endgroup\$
    – Neil
    Apr 3 '20 at 10:28
7
\$\begingroup\$

Haskell, 124 121 99 88 bytes

3 bytes saved by Bubbler

x%y=[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 a modification of the below algorithm which uses a bit of complex short-circuiting to accomplish the task.

I owe much to xnor's comment that initially proposed the idea, and to Noughtmare's SO answer which explained why xnor's initial version didn't work.

99 Bytes

x%y=2==(x#y)0
(u@(a:b)#v@(c:d))x|a==c=b#d$x|x<2=minimum$[d#u,b#v,b#d]<*>[x+1]
(a#b)x=x+length(a++b)

Try it online!

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 2 times and we would branch another time, we can just stop there and say return the total we have for the branch. All values above 2 are the same as far as we are concerned.

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

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

\$\endgroup\$
6
  • 2
    \$\begingroup\$ 121 \$\endgroup\$
    – Bubbler
    Apr 3 '20 at 2:26
  • 1
    \$\begingroup\$ I was trying to use Haskell's lazy evaluation to shortcut edit distance greater than 2, but it seems not to work: TIO. Not sure why. I thought that since, say, min[0,0][0,0..] short-circuits evaluation it's wouldn't evaluate branches with with results above [0,0] for distance 2. \$\endgroup\$
    – xnor
    Apr 3 '20 at 3:39
  • \$\begingroup\$ I timed it with two strings of length 100k and 100k - 1. It takes about 1s which indicates to me it is linear but do you understand why it is taking that long? The Retina solution takes about 1/10th of the time. \$\endgroup\$
    – user9207
    Apr 3 '20 at 10:03
  • 1
    \$\begingroup\$ @Anush An empty Haskell program on TIO also seems to take about a second to run. \$\endgroup\$
    – xnor
    Apr 3 '20 at 12:47
  • \$\begingroup\$ @xnor Aha! That solves it. \$\endgroup\$
    – user9207
    Apr 3 '20 at 12:50
4
\$\begingroup\$

Python 3.8, 273 \$\cdots\$316 312 bytes

Added 30 bytes to fix bugs kindly pointed out by Bubbler.
Added 12 bytes to fix a bug kindly pointed out by ovs.
Saved 9 bytes thanks to ovs!!!

def f(*x,i=0):
 b,a=w=sorted(x,key=len);d,c=map(len,w)
 while a[i]==b[i]:
  if(i:=i+1)==d:return i==c-2
 while a[c-1]==b[d-1]:
  if d==1:return c==3
  c-=1;d-=1
 a=a[i:c]
 b=b[i:d]
 return c-i>1and((x:=a[1:-1])==(y:=b[1:-1])or a[:-1]==y or a[1:]==y or a[:-1]==b[1:]or a[1:]==b[:-1]or x==b[:-1]or x==b[1:]or x==b)

Try it online!

\$\endgroup\$
11
  • \$\begingroup\$ This fails with a max recursion depth error for strings that aren't very short. This means I can't test if it is really running in linear time. \$\endgroup\$
    – user9207
    Apr 3 '20 at 9:02
  • \$\begingroup\$ I think a[1:] is linear time itself in python at it copies the list. \$\endgroup\$
    – user9207
    Apr 3 '20 at 12:59
  • \$\begingroup\$ I get a syntax error when I try to run the code now. bpaste.net/NXVQ \$\endgroup\$
    – user9207
    Apr 3 '20 at 16:19
  • \$\begingroup\$ Could you paste a standalone python program to bpaste.net please? \$\endgroup\$
    – user9207
    Apr 3 '20 at 16:35
  • \$\begingroup\$ @Anush It's probably using version less than Python 3.8. Run it on your laptop with Python 3.8. \$\endgroup\$
    – Noodle9
    Apr 3 '20 at 16:37
3
\$\begingroup\$

JavaScript, 120 bytes

a=>b=>a.reduce((t,c,i)=>t.map((n,j)=>p=Math.min(n-(c==b[i+j-2]),p,t[j+1]||4)+1,p=4),[4,4,1,2,3])[b.length-a.length+2]==3

Try it online!

Try a large one!

Traditional DP solution, with modification the formula by \$dp_{i,k}=\infty \text{ if } \left|i-k\right|>2 \$. And we use \$ k=i+j-2 \$ here.

t is initialed to [4,4,1,2,3] which means (the edit distance of an empty string and first j-2 characters of b) plus 1. Any number greater than 3 here means Infinity. After i-th iteration, t[j] is (the edit distance of substring a[0..i], and, b[0..(i+j-2)]) plus 1; Or anything greater than 3 if the edit distance is greater than 2.

\$\endgroup\$
5
  • \$\begingroup\$ Could you add some explanation please? Have you tried it on two strings of length roughly 100,000? \$\endgroup\$
    – Anush
    Aug 31 at 9:05
  • \$\begingroup\$ @Anush As it only contains 2 nested loops, one repeat a.length times, and the inner one repeat 5 times. It will cost O(a.length*5) time to run, which meet the complexity requirement. \$\endgroup\$
    – tsh
    Aug 31 at 11:35
  • \$\begingroup\$ @Anush And do you mean add some testcases like this one? \$\endgroup\$
    – tsh
    Aug 31 at 11:53
  • \$\begingroup\$ Thank you. What do the magic numbers 4,4,1,2,3 signify? \$\endgroup\$
    – Anush
    Aug 31 at 11:54
  • \$\begingroup\$ Thank you for adding that test case! \$\endgroup\$
    – Anush
    Aug 31 at 11:55

Your Answer

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