10
\$\begingroup\$

Given two strings \$A\$ and \$B\$ with edit (Levenshtein) distance \$x\$, find a third string with edit distance \$a\$ to \$A\$ and edit distance \$b\$ to \$B\$ so that \$a+b=x\$ and \$a=int(x/2)\$ (that is half of \$x\$ rounded down to the nearest integer).

The input is the two strings \$A\$ and \$B\$ and their edit distance \$x\$. You don’t need to compute \$x\$.

\$A\$ is of length \$n\$ and \$B\$ is of length \$m\$ such that \$n/2 \le m \le n\$.

Your can take the input in any convenient format you like.

Examples

Inputs: "hello", "hallo", 1. Output: "hello"

Inputs: "sitteng", "kitten", 2. Output: "sitten"

Inputs: "bijamas", "banana", 4. Output: "banamas"

Inputs: "Pneumonoultramicroscopicsilicovolcanoconiosis", "noultramicroscopicsilicovolcanoconiosis", 6. Output: "umonoultramicroscopicsilicovolcanoconiosis"

Restriction

Your code must be run in \$O(n^2)\$ time where \$n\$ is the length of A.

\$\endgroup\$
5
  • \$\begingroup\$ Missing "...where N is X" for the restriction \$\endgroup\$
    – mousetail
    Aug 26, 2023 at 10:28
  • \$\begingroup\$ @mousetail Better now? \$\endgroup\$
    – Simd
    Aug 26, 2023 at 10:37
  • \$\begingroup\$ You say "A is of length n and B is of length n/2 ≤ m ≤ n", however, you never defined m, and B is certainly not half the length of A in the given examples... \$\endgroup\$
    – mbomb007
    Aug 26, 2023 at 15:47
  • \$\begingroup\$ @mbomb007 I edited it. Is that better? \$\endgroup\$
    – The Thonnu
    Aug 26, 2023 at 15:53
  • \$\begingroup\$ @TheThonnu Yes, that looks correct. \$\endgroup\$
    – mbomb007
    Aug 28, 2023 at 17:01

2 Answers 2

6
+50
\$\begingroup\$

Python, 459 514 502 bytes

+60 bytes, use correct initial condition
-11 bytes, thanks to ValueInk
-1 byte, thanks to c--

l=len
I=range
def f(s,t):
 m,n=l(s),l(t);w=m-~n;M=[[([t[:k]+s for k in I(j+1)],j)for j in I(n+1)]]+[[([s[k:]for k in I(i+2)],0)]+n*[0]for i in I(m)]
 for j in I(n):
  for i in I(m):D,d=M[i][j+1];U,u=M[i+1][j];R,r=M[i][j];a=l(D:=D+[p[:d]+p[d+1:]])if(p:=D[-1])[:d]==t[:d]else w;b=l(U:=U+[p[:u]+[t[j]]+p[u:]])if(p:=U[-1])[:u]==t[:u]else w;c=l(R:=R+[[],[p[:r]+[t[r]]+p[r+1:]]][p[r]!=t[r]])if(p:=R[-1])[:r]==t[:r]else w;M[i+1][j+1]={b:(U,u+1),c:(R,r+1),a:(D,d)}[min(a,b,c)]
 return(p:=M[m][n][0])[~-l(p)//2]

Attempt This Online!

Input&Output as lists of characters.

For some examples the result is different from the result in the question, but also satisfies the distance requirement

Explanation

Uses modified version of the dynamic programming algorithm for the computation of the Levenshtein distance. Each cell stores the current prefix length and the path of all previous edits. At the end the cell in the middle of the path is returned.

ungolfed code:

def levDist(s,t):
  m,n=len(s),len(t)
  w=m+n+1 # one larger than the largest possible Levenshtein distance
  M=[]
  # initialize first row and column
  for i in range(0, m+1):
    M.append([([s[k:] for k in range(i+1)],0)]+[0]*n)
  for j in range(1, n+1):
    M[0][j]=([t[:k]+s for k in range(j+1)],j)
  for j in range(0, n):
    for i in range(0, m):
      # cell i,j -> shortest edit path that:
      # 1) only modifies the first i characters in s 
      # 2) ends with a word starting with the first j characters in t 
      D,d=M[i][j+1] # deletion
      U,u=M[i+1][j] # insertion
      R,r=M[i][j]   # substitution
      # for each edit type check if the previous cell contains the correct prefix and if yes perform the repetitive edit
      if (p:=D[-1])[:d]==t[:d]:
        D=D+[p[:d]+p[d+1:]]
        a=len(D)
      else:
        a=w
      if (p:=U[-1])[:u]==t[:u]:
        U=U+[p[:u]+[t[j]]+p[u:]]
        b=len(U)
      else:
        b=w
      if (p:=R[-1])[:r]==t[:r]:
        if p[r]!=t[r]:
          R=R+[p[:r]+[t[r]]+p[r+1:]]
        c=len(R)
      else:
        c=w
      x=min(a,b,c) # find operation with the shortest edit path
      if x==a:
        M[i+1][j+1] = (D,d)
      elif x==b:
        M[i+1][j+1] = (U,u+1)
      else:
        M[i+1][j+1] = (R,r+1)
  return ((p:=M[m][n][0])[(len(p)-1)//2],M[m][n]) # the ungolfed version also returns the complete edit path

Attempt This Online!

\$\endgroup\$
5
  • \$\begingroup\$ This is a very nice solution. \$\endgroup\$
    – Simd
    Aug 27, 2023 at 19:07
  • \$\begingroup\$ Can you explain more about the initial condition fix? \$\endgroup\$
    – Simd
    Aug 28, 2023 at 10:21
  • 1
    \$\begingroup\$ @Simd In the old version the edit distance for the last example was wrong (7 instead of 6). The new initial condition corresponds to the edits that are used in the initial condition of the distance algorithm. \$\endgroup\$
    – bsoelch
    Aug 28, 2023 at 10:51
  • \$\begingroup\$ ~-l(p)//2 to save 2 bytes \$\endgroup\$
    – Value Ink
    Aug 28, 2023 at 19:17
  • \$\begingroup\$ I just double checked and Python dict allows for duplicate keys during declaration (the lattermost will take precedence) which means you should be able to do {a:(D,d),b:(U,u+1),c:(R,r+1)}[min(a,b,c)] instead of the index strategy for -9. \$\endgroup\$
    – Value Ink
    Aug 28, 2023 at 19:47
3
\$\begingroup\$

Haskell, 182 175 bytes, not in \$O(n^2)\$

-7 bytes thanks to @Wheat Wizard

import Data.List
l=length
(x:w)#(y:z)|x==y=map(x:)$w#z
a@(x:w)#b|y:z<-b=sortOn l[a:w#b,a#z++[b],a:map(y:)(w#z)]!!0|1>0=a:w#[]
_#(y:z)=[]#z++[y:z]
_#_=[[]]
a%b=b#a!!div(l$b#a)2

Attempt This Online!


Edit: I remembered that the Levenshtein distance could be calculated in quadratic time, but I didn't remember which algorithm was the one with this time complexity and I didn't bother to check the complexity of the naive one.

\$\endgroup\$
7
  • \$\begingroup\$ Thanks for giving the first answer! \$\endgroup\$
    – Simd
    Aug 26, 2023 at 19:36
  • \$\begingroup\$ You can save 2 bytes by replacing head with !!0. \$\endgroup\$
    – Wheat Wizard
    Aug 26, 2023 at 20:03
  • \$\begingroup\$ You can also combine the 4th and 6th lines into a@(x:w)#b|y:z<-b=sortOn l[a:w#b,a#z++[b],a:map(y:)(w#z)]!!0|1>0=a:w#[], to save 5 more bytes. \$\endgroup\$
    – Wheat Wizard
    Aug 26, 2023 at 20:06
  • 3
    \$\begingroup\$ Are you sure this runs in quadratic time? \$\endgroup\$
    – xnor
    Aug 26, 2023 at 21:56
  • 3
    \$\begingroup\$ I fear your code might take exponential time. Try it with strings of length 50 to 100. \$\endgroup\$
    – Simd
    Aug 27, 2023 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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