# Levenshtein Distance

While there are many edit distance questions, such as this one, there isn't a simple question to write a program that calculates the Levenshtein distance.

Some Exposition

The Levenshtein edit distance between two strings is the minimum possible number of insertions, deletions, or substitutions to convert one word into another word. In this case, each insertion, deletion and substitution has a cost of 1.

For example, the distance between roll and rolling is 3, because deletions cost 1, and we need to delete 3 characterrs. The distance between toll and tall is 1, because substitutions cost 1.

Rules

• The input will be two strings. You may assume that the strings are lowercase, only contain letters, are non-empty and are a maximum of 100 characters in length.
• The output will be minimum Levenshtein edit distance of the two strings, as defined above.
• Your code must a program or a function. It does not need to be a named function, but it cannot be a built-in function that directly computes the Levenshtein distance. Other built-ins are allowed.
• This is code golf, so the shortest answer wins.

Some Examples

>>> lev("atoll", "bowl")
3
>>> lev("tar", "tarp")
1
>>> lev("turing", "tarpit")
4
>>> lev("antidisestablishmentarianism", "bulb")
27

As always, if the problem is unclear, please let me know. Good luck and good golfing!

# Pyth, 34 bytes

J]wf}z=Jsmsm++.DdkXLdkGXLkdGhld-Jk

Demonstration

This is not particularly well golfed, and very slow. It can't handle anything past 2 changes in a reasonable period of time.

• But it works, and that's what counts. :P – Conor O'Brien Dec 28 '15 at 23:54

# Matlab, 177 163 bytes

function l=c(a,b);m=nnz(a)+1;n=nnz(b)+1;for i=0:m-1;for j=0:n-1;z=max(i,j);try;z=min([l(i,j+1)+1,l(i+1,j)+1,l(i,j)+(a(i)~=b(j))]);end;l(i+1,j+1)=z;end;end;l=l(m,n)

This is a straightforward implementation of this formula:

Ungolfed:

function l=l(a,b);
m=nnz(a)+1;
n=nnz(b)+1;
for i=0:m-1;
for j=0:n-1;
z=max(i,j);
try;
z=min([l(i,j+1)+1,l(i+1,j)+1,l(i,j)+(a(i)~=b(j))]);
end;
l(i+1,j+1)=z;
end;
end;
l=l(m,n)
• If the scored code is not what you've included, please include the scored code. Otherwise I think there's a lot of whitespace that can be golfed out. – Alex A. Dec 23 '15 at 17:04
• @AlexA. the leading space and newlines for indentation purpose are not counted (and can be removed safely). Unce upon a time this was allowed and no one complained. – edc65 Dec 23 '15 at 18:28
• @edc65 The meta consensus now is that the code as scored should be provided. – Alex A. Dec 23 '15 at 18:34
• Well then, the majority prefers the unreadable version. I still let the readable version here, in case anyone might want to see what is actually going on=) – flawr Dec 23 '15 at 20:28
• It's common practice to provide both the golfed submission (the one that's scored) as well as an ungolfed version, we just require that the scored one be included. ;) – Alex A. Dec 24 '15 at 17:35

# Python 2, 151140 138 bytes

Slow recursive implemention of the Levenshtein distance based on Wikipedia (Thanks to @Kenney for shaving of 11 chars and @Sherlock9 for another 2).

def l(s,t):
def f(m,n):
if m*n<1:return m or n
return 1+min([f(m-1,n),f(m,n-1),f(m-1,n-1)-(s[m-1]==t[n-1])])
return f(len(s),len(t))

Giving the correct answers for the presented test cases:

assert l("tar", "tarp") == 1
assert l("turing", "tarpit") == 4
assert l("antidisestablishmentarianism", "bulb") == 27
assert l("atoll", "bowl") == 3
• You might save 3-4 bytes or so by doing something like if !n*m:return n if n else m, and another 2 by return 1+min([ f(..), f(..), f(..) - (s[..] == t[..]) ]). – Kenney Dec 24 '15 at 21:10
• You would save 2 bytes by using f(m-1,n-1)-(s[m-1]==t[n-1]) instead of f(m-1,n-1)+(s[m-1]!=t[n-1])-1. – Sherlock9 Dec 29 '15 at 3:45
• Golfed off 20 chars: codegolf.stackexchange.com/a/102910/60919 – FlipTack Dec 11 '16 at 14:46

# JavaScript (ES6) 106 113 122

Edit 16 bytes saved following @Neil suggestions

As an anonymous function.

(s,t)=>[...s].map((u,i)=>w=w.map((v,j)=>p=j--?Math.min(p,v,w[j]-(u==t[j]))+1:i+1),w=[...[,...t].keys()])|p

This is a golfed implementation of the Wagner–Fischer algorithm exactly as described in the linked wikipedia article, in the section Iterative with two matrix rows (even if in fact, just 1 row is used - array w)

Less golfed

(s,t)=>
{
w = [...[0,...t].keys()];
for(i = 0; i < s.length; i++)
w = w.map((v,j)=>
p = j
? Math.min(p+1, v+1, w[j-1] + (s[i]!=t[j-1]))
: i+1
);
return p
}

Test snippet

L=(s,t)=>[...s].map((u,i)=>w=w.map((v,j)=>p=j--?Math.min(p,v,w[j]-(u==t[j]))+1:i+1),w=[...[,...t].keys()])|p

console.log=x=>O.textContent+=x+'\n';

[["atoll", "bowl"],["tar", "tarp"]
,["turing", "tarpit"],["antidisestablishmentarianism", "bulb"]]
.forEach(t=>console.log(t+' => '+L(...t)))
<pre id=O></pre>

• Can you use [...[0,...t].keys()] instead? Saves 2 bytes if you can. – Neil Dec 23 '15 at 16:12
• @Neil that looks ugly but it's shorter. Thx – edc65 Dec 23 '15 at 16:41
• Actually you can save another byte, [...[,...t].keys()] works too I think. – Neil Dec 23 '15 at 22:17
• I managed to shave off another byte by using [...s].map(): (s,t)=>(w=[...[,...t].keys()],[...s].map((u,i)=>w=w.map((v,j)=>p=j--?Math.min(p,v,w[j]-(s[i-1]==t[j]))+1:i)),p) – Neil Dec 23 '15 at 22:28
• @Neil great, thanks again! – edc65 Dec 23 '15 at 22:44

# APL (Dyalog Classic), 34 bytes

{0∊≢¨⍵:≢∊⍵⋄⌊/(≢.↑+∘∇↓¨)∘⍵¨1↓,⍳2 2}

Try it online!

• This fails for 'help' f 'department' – H.PWiz Apr 20 at 17:48
• And 'look' f 'calculate' (for a different reason, I think) – H.PWiz Apr 20 at 22:41
• @H.PWiz fixed, thanks. different approach but luckily same byte count. – ngn Apr 22 at 16:55

# Python 2, 118 bytes

A golf of this solution, but it doesn't look like Willem's been on for a year, so I'll have to post it myself:

def l(s,t):f=lambda m,n:m or n if m*n<1else-~min(f(m-1,n),f(m,n-1),f(m-1,n-1)-(s[m-1]==t[n-1]));print f(len(s),len(t))

Try on repl.it

Takes two strings and outputs the distance to STDOUT (allowed by meta). Please comment suggestions, I'm sure this can be golfed further.

• Is it necessary to wrap everything in a function? Could you use two input()s or an input().split()? – Sherlock9 Dec 11 '16 at 14:46
• @Sherlock9 I tried that, but it costs 1 byte extra as far as I can tell – FlipTack Dec 11 '16 at 15:29
• Right, I forgot that you need to define s and t somewhere in the code. Never mind. Good job :D – Sherlock9 Dec 11 '16 at 16:27
• I'm not sure why Willem used m or n. You can replace it with m+n. – Arnauld Apr 27 '19 at 7:05

e@(a:r)#f@(b:s)|a==b=r#s|1<3=1+minimum[r#f,e#s,r#s]
x#y=length$x++y Try it online! Example usage: "turing" # "tarpit" yields 4. This is a recursive solution. Given two strings e and f, we first compare their first characters a and b. If they are equal, then the Levenshtein distance of e and f is the same as the Levenshtein distance of r and s, the remainder of e and f after removing the first characters. Otherwise, either a or b needs to be removed, or one is substituted by the other. [r#f,e#s,r#s] recursively computes the Levenshtein for those three cases, minimum picks the smallest one, and 1 is added to account for the necessary remove or replace operation. If one of the strings is empty, we and up on the second line. In this case, the distance is just the length of the non-empty string, or equivalently the length of both strings concatenated together. • Wow, this is a seriously good solution, really elegant and short. – ggPeti Mar 6 '18 at 23:08 • It seems your program outputs 0 for the input pair "abb","aab" (link). (I just found out because I wanted to steal your code for another challenge:) – flawr Dec 29 '19 at 21:49 • @flawr Thanks for pointing out, the previous 67 byte version works correctly so I rolled back. – Laikoni Dec 31 '19 at 0:28 # Python 3, 267216184 162 bytes This function calculates the Levenshtein distance using an array that is 2 x len(word_2)+1 in size. Edit: This doesn't get close to the Willem's Python 2 answer, but here is a more golfed answer with many little refinements here and there. def e(p,q): m=len(q);r=range;*a,=r(m+1);b=[1]*-~m for i in r(len(p)): for j in r(m):b[j+1]=1+min(a[j+1],b[j],a[j]-(p[i]==q[j])) a,b=b,[i+2]*-~m return a[m] Ungolfed: def edit_distance(word_1,word_2): len_1 = len(word_1) len_2 = len(word_2) dist = [[x for x in range(len_2+1)], [1 for y in range(len_2+1)]] for i in range(len_1): for j in range(len_2): if word_1[i] == word_2[j]: dist[1][j+1] = dist[0][j] else: deletion = dist[0][j+1]+1 insertion = dist[1][j]+1 substitution = dist[0][j]+1 dist[1][j+1] = min(deletion, insertion, substitution) dist[0], dist[1] = dist[1], [i+2 for m in range(len_2+1)] return dist[0][len_2] # AutoIt, 333 bytes Func l($0,$1,$_=StringLen,$z=StringMid) Dim$2=$_($0),$3=$_($1),$4[$2+1][$3+1]
For $5=0 To$2
$4[$5][0]=$5 Next For$6=0 To $3$4[0][$6]=$6
Next
For $5=1 To$2
For $6=1 To$3
$9=$z($0,$5,1)<>$z($1,$6,1)$7=1+$4[$5][$6-1]$8=$9+$4[$5-1][$6-1]
$m=1+$4[$5-1][$6]
$m=$m>$7?$7:$m$4[$5][$6]=$m>$8?$8:$m
Next
Next
Return $4[$2][$3] EndFunc Sample test code: ConsoleWrite(l("atoll", "bowl") & @LF) ConsoleWrite(l("tar", "tarp") & @LF) ConsoleWrite(l("turing", "tarpit") & @LF) ConsoleWrite(l("antidisestablishmentarianism", "bulb") & @LF) yields 3 1 4 27 ## k4, 66 bytes {$[~#x;#y;~#y;#x;&/.z.s'[-1 0 -1_\:x;0 -1 -1_\:y]+1 1,~(*|x)=*|y]}

A boring and basically ungolfed impl of the algo. Ex.:

f:{$[~#x;#y;~#y;#x;&/.z.s'[-1 0 -1_\:x;0 -1 -1_\:y]+1 1,~(*|x)=*|y]} f["kitten";"sitting"] 3 f["atoll";"bowl"] 3 f["tar";"tarp"] 1 f["turing";"tarpit"] 4 f["antidisestablishmentarianism";"bulb"] 27 ## Seriously, 8682 78 bytes ,#,#k;;;░="+l"£@"│d);)[]oq╜Riu)@d);)@[]oq╜Riu(@)@)@[]oq╜Ri3}@)=Y+km"£@IRi;╗ƒ Hex Dump: 2c232c23606b3b3b3bb03d222b6c229c4022b364293b295b5d6f71bd526975294064293b29405b 5d6f71bd5269752840294029405b5d6f71bd5269337d40293d592b6b6d229c40495269603bbb9f Try It Online (Note that the link is to a different version because something about the online interpreter breaks with the new, shorter version, even though it works fine with the downloadable interpreter.) It's about the most straightforward implementation Seriously allows for the recursive definition. It is very slow because it does no memoization at all. Perhaps the tabular method could be shorter (maybe by using the registers as rows), but I'm fairly happy with this, despite how much kludging-my-way-around-the-language's-shortcomings it contains. That one can use []oq<code>Ri as a proper two-argument function call was quite the nice find. Explanation: ,#,# Read in two arguments, break them into lists of chars  ;╗ƒ put the quoted function in reg0 and immediately call it k;;; put the two lists in a list and make 3 copies ░ replace the latter two with one with empty lists removed = replace two more with 1 if no empty lists removed, else 0 "..."£@"..."£@ push the two functions described below, moving the boolean above them both I select the correct function based on the condition Ri call the function, returning the correct distance for these substrings There are two functions that can be called from the main function above. Each expects two strings, i and j, to be on the stack. This situation is ensured by putting those strings in a list and using R to call the functions with that list as the stack. The first is very simple: +l Concatenate the strings and take their length. This is equivalent to the length of the longer string, since one of the strings will be empty. The second function is very long and complicated. It will do the "insertion, deletion, substitution" part of the recursive definition. Here's what happens in 4 parts: │d);) After this, the stack is top[i-,j,i,j,ci,i-], where i- is list i with its last character, ci, chopped off. []oq this puts i- and j into a list so that they can be passed as arguments recursively into the main function ╜Riu this calls the main function (from reg0) with the args which will return a number to which we add 1 to get #d, the min distance if we delete a character )@d);)@ After this, the stack is top[i,j-,ci,i-,#d,cj,j-], where j- and cj are the same idea as i- and ci []oq╜Riu listify arguments, recurse and increment to get #i (distance if we insert) (@)@)@ After this, the stack is top[i-,j-,#d,cj,#i,ci] []oq╜Ri listify arguments, recurse to get min distance between them but we still need to add 1 when we'd need to substitute because the chars we chopped off are different (((@) After this, the stack is top[cj,ci,#s,#d,#i] =Y 1 if they are not equal, 0 if they are + add it to the distance we find to get the distance if we substitute here k put them all in a list m push the minimum distance over the three options • I like how the code tries to escape the pre-element :) – mınxomaτ Dec 23 '15 at 11:36 # Retina, 78 72 bytes &`(.)*$(?<!(?=((?<-4>\4)|(?<-1>.(?<-4>)?))*,(?(4),))^.*,((.)|(?<-1>.))*)

Try it online!

In a way, this is a pure regex solution where the result is the number of positions from which the regex matches. Because why not...

Fair warning, this is super inefficient. The way this works is that it offloads the actual optimisation to the regex engine's backtracker, which simply brute forces all possible alignments, starting with as few alterations as possible and allowing one more until it's possible to match up the strings with additions, deletions and substitutions.

For a slightly more sensible solution, this one does the matching only once and doesn't have any negative lookarounds. Here, the result is the number of captures in group 2, which you could access with match.Groups[2].Captures.Count in C#, for example. It's still horribly inefficient though.

## Explanation

I'm explaining the second version above, because it's conceptually a bit easier (as it's just a single regex match). Here is an ungolfed version I've named the groups (or made them non-capturing) and added comments. Remember that the components in a lookbehind should be read from back to front, but alternatives and lookaheads inside those should be read from front to back. Yeah.

.+                      # Ensures backtracking from smallest to largest for next repetition
(?<ops>(?<distance>.))* # This puts the current attempted distances onto two different stacks,
# one to work with, and one for the result.
$# Make sure the lookbehind starts from the end. (?<= # The basic idea is now to match up the strings character by character, # allowing insertions/deletions/substitutions at the cost of one capture # on <ops>. Remember to read from the bottom up. (?= # Start matching forwards again. We need to go through the other string # front-to-back due to the nature of the stack (the last character we # remembered from the second string must be the first character we check # against in the first string). (?: (?<-str>\k<str>) # Either match the current character against the corresponding one from # the other string. | (?<-ops> # Or consume one operation to... . # consume a character without matching it to the other string (a deletion) (?<-str>)? # optionally dropping a character from the other string as well # (a substitution). ) )* # Rinse and repeat. ,(?(str),) # Ensure we reached the end of the first string while consuming all of the # second string. This is only possible if the two strings can be matched up # in no more than <distance> operations. ) ^.*, # Match the rest of string to get back to the front. (?: # This remembers the second string from back-to-front. (?<str>.) # Either capture the current character. | (?<-ops>.) # Or skip it, consuming an operation. This is an insertion. )* ) The only difference to the 72-byte version is that we can drop the leading .+ (and second group in the beginning) by finding positions at the end where we don't have enough <ops> and count all of those positions. # Haskell, 136 bytes Call e. Bit slow on antidisestablishmentarianism etc. l=length e a b=v a(l a)b(l b) v a i b j|i*j==0=i+j|0<1=minimum[1+v a(i-1)b j,1+v a i b(j-1),fromEnum(a!!(i-1)/=b!!(j-1))+v a(i-1)b(j-1)] # Jolf, 4 bytes Try it here! ~LiI ~L calculate the Levenshtein distance of i input string I and another input string I added that builtin yesterday, but saw this challenge today, i.e., just now. Still, this answer is noncompeting. In a newer version: ~Li takes implicit second input. • "Your code must a program or a function. It does not need to be a named function, but it cannot be a built-in function that directly computes the Levenshtein distance. Other built-ins are allowed." – Kevin Cruijssen Jun 14 '18 at 14:17 • Ah, didn't see you mentioned it's non-competing.. Better put it in the title, or add a valid program/function without builtin. – Kevin Cruijssen Jun 14 '18 at 14:19 # GNU Prolog, 133 bytes m([H|A],B):-B=A;B=[H|A]. d([H|A]-[H|B],D):-d(A-B,D). d(A-B,D):-A=B,D=0;D#=E+1,m(A,X),m(B,Y),d(X-Y,E). l(W,D):-d(W,D),(E#<D,l(W,E);!). Takes a tuple as argument. Example of usage: | ?- l("turing"-"tarpit",D). D = 4 yes m specifies that B is A either directly or with its first character removed. d uses m as a subroutine to calculate an edit distance between the tuple elements (i.e. the distance of a series of edits that converts one into the other). Then l is a standard trick for finding the minimum of d (you take an arbitrary distance, then take an arbitrary smaller distance, repeat until you can't go smaller). # Python 3, 10594 93 bytes -11 bytes by xnor l=lambda a,b:b>""<a and min(l(a[1:],b[1:])+(a[0]!=b[0]),l(a[1:],b)+1,l(a,b[1:])+1)or len(a+b) Golfed version of the shortest implementation on Wikibooks. Try it online! • Nice solution. The l= needs to be included and counted because the function is recursive. You can combine the bases cases into if b>""<a else len(a+b). – xnor Apr 27 '19 at 22:54 • Nice play with the operators, thanx! – movatica Apr 27 '19 at 23:38 # JavaScript (ES6), 95 91 89 bytes Takes input as (source)(target). Essentially a port of @Willem's Python answer (later optimized by @FlipTack). s=>t=>(g=m=>m*n?1+Math.min(g(m,--n),g(--m)-(s[m]==t[n++]),g(m)):m+n)(s.length,n=t.length) Try it online! # Perl, 168166 163 bytes sub l{my($S,$T,$m)=(@_,100);$S*$T?do{$m=++$_<$m?$_:$m for l($S-1,$T),l($S,--$T),l(--$S,$T)-($a[$S]eq$b[$T]);$m}:$S||$T}print l~~(@a=shift=~/./g),~~(@b=shift=~/./g)

Recursive implementation. Save in a file.pl and run as perl file.pl atoll bowl.

sub l {
my($S,$T,$m)=(@_,100);$S*$T ? do {$m = ++$_ <$m ? $_ :$m
for
l($S-1,$T),
l($S , --$T),
l(--$S,$T) - ($a[$S] eq $b[$T])
;
$m } :$S||$T } print l~~(@a=shift=~/./g),~~(@b=shift=~/./g) The other two implementations are both longer (full matrix: 237 bytes, twoone-row iterative: 187). • update 166: omit () in calling l. • update 163: eliminate return by abusing do in trinary. # C, 192 bytes #define m(x,y) (x>y?x:y) #define r(x,y) l(s,ls-x,t,lt-y) int l(char*s,int ls,char*t,int lt){if(!ls)return lt;if(!lt)return ls;a=r(1,1);if(s[ls]==t[ls])return a;return m(m(r(0,1),r(1,0)),a)+1;} --------- Detailed #include <stdio.h> #define m(x,y) (x>y?x:y) #define f(x) char x[128];fgets(x,100,stdin) #define r(x,y) l(s,ls-x,t,lt-y) int l(char*s,int ls,char*t,int lt) { if(!ls) return lt; if(!lt) return ls; int a = r(1,1); if(s[ls]==t[ls]) return a; return m(m(r(0,1),r(1,0)),a)+1; } int main(void) { f(a); f(b); printf("%d", l(a,strlen(a),b,strlen(b))); return 0; } # C#, 215210 198 public int L(string s,string t){int c,f,a,i,j;var v=new int[100];for(c=i=0;i<s.Length;i++)for(f=c=i,j=0;j<t.Length;j++){a=c;c=f;f=i==0?j+1:v[j];if(f<a)a=f;v[j]=c=s[i]==t[j]?c:1+(c<a?c:a);}return c;} more readable: public int L(string s,string t){ int c,f,a,i,j; var v=new int[100]; for(c=i=0;i<s.Length;i++) for(f=c=i,j=0;j<t.Length;j++){ a=c; c=f; f=(i==0)?j+1:v[j]; if (f<a) a=f; v[j]=c=(s[i]==t[j])?c:1+((c<a)?c:a); } return c; } ## PowerShell v3+, 247 Bytes$c,$d=$args;$e,$f=$c,$d|% le*;$m=[object[,]]::new($f+1,$e+1);0..$e|%{$m[0,$_]=$_};0..$f|%{$m[$_,0]=$_};1..$e|%{$i=$_;1..$f|%{$m[$_,$i]=(($m[($_-1),$i]+1),($m[$_,($i-1)]+1),($m[($_-1),($i-1)]+((1,0)[($c[($i-1)]-eq$d[($_-1)])]))|sort)[0]}};$m[$f,$e]

I ended up making this to solve another challenges involving LD's.

# Get both of the string passed as arguments. $c being the compare string # and$d being the difference string.
$c,$d=$args # Save the lengths of these strings.$e is the length of $c and$f is the length of $d$e,$f=$c,$d|% le* # Create the multidimentional array$m for recording LD calculations
$m=[object[,]]::new($f+1,$e+1) # Populate the first column 0..$e|%{$m[0,$_]=$_} # Populate the first row 0..$f|%{$m[$_,0]=$_} # Calculate the Levenshtein distance by working through each position in the matrix. # Working the columns 1..$e|%{
$i=$_
1..$f|%{ # Calculate the smallest value between the following values in the matrix relative to this one # cell above, cell to the left, cell in the upper left. # Upper left also contain the cost calculation for this pass.$m[$_,$i]=(($m[($_-1),$i]+1),($m[$_,($i-1)]+1),($m[($_-1),($i-1)]+((1,0)[($c[($i-1)]-eq$d[($_-1)])]))|sort)[0] } } # Return the last element of the matrix to get LD$m[$f,$e]