Meskipun ada banyak pertanyaan edit jarak, seperti ini , tidak ada pertanyaan sederhana untuk menulis sebuah program yang menghitung jarak Levenshtein.

Beberapa Eksposisi

Jarak edit Levenshtein antara dua string adalah jumlah penyisipan, penghapusan, atau penggantian minimum yang mungkin untuk mengubah satu kata menjadi kata lain. Dalam hal ini, setiap penyisipan, penghapusan dan penggantian memiliki biaya 1.

Misalnya, jarak antara rolldan rolling3, karena penghapusan berharga 1, dan kita perlu menghapus 3 karakter. Jarak antara tolldan tall1, karena biaya penggantian 1.

Aturan

• Input akan terdiri dari dua string. Anda dapat mengasumsikan bahwa string adalah huruf kecil, hanya berisi huruf, tidak kosong dan panjang maksimal 100 karakter.
• Outputnya adalah jarak edit Levenshtein minimum dari dua string, seperti yang didefinisikan di atas.
• Kode Anda harus berupa program atau fungsi. Itu tidak perlu menjadi fungsi bernama, tetapi tidak bisa menjadi fungsi bawaan yang secara langsung menghitung jarak Levenshtein. Built-in lainnya diizinkan.
• Ini kode golf, jadi jawaban tersingkat menang.

Beberapa contoh

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

Seperti biasa, jika masalahnya tidak jelas, beri tahu saya. Semoga berhasil dan bermain golf dengan baik!

Katalog

var QUESTION_ID=67474;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}

body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>

Pyth, 34 byte

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

Demonstrasi

Ini tidak golf dengan baik, dan sangat lambat. Itu tidak dapat menangani apa pun melewati 2 perubahan dalam periode waktu yang wajar.

Matlab, 177 163 byte

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)

Ini adalah implementasi langsung dari rumus ini:

Tidak Disatukan:

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)

Python 2, 151 140 138 byte

Implementasi rekursif lambat dari jarak Levenshtein berdasarkan Wikipedia (Terima kasih kepada @Kenney karena telah mencukur 11 karakter dan @ Sherlock9 untuk 2 yang lain).

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))

Memberikan jawaban yang benar untuk kasus uji yang disajikan:

assert l("tar", "tarp") == 1
assert l("turing", "tarpit") == 4
assert l("antidisestablishmentarianism", "bulb") == 27        
assert l("atoll", "bowl") == 3

JavaScript (ES6) 106 113 122

Edit 16 byte yang disimpan mengikuti saran @Neil

Sebagai fungsi anonim.

(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

Ini adalah implementasi golf dari algoritma Wagner-Fischer persis seperti yang dijelaskan dalam artikel wikipedia tertaut, di bagian Iterative dengan dua baris matriks (bahkan jika kenyataannya, hanya 1 baris digunakan - array w )

Kurang golf

(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
}

Cuplikan tes

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>

Python 2, 118 byte

Sebuah golf dari solusi ini , tetapi sepertinya Willem tidak ada selama setahun, jadi saya harus mempostingnya sendiri:

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))

Coba di repl.it

Mengambil dua string dan menampilkan jarak ke STDOUT( diizinkan oleh meta ). Silakan komentar saran, saya yakin ini bisa golf lebih lanjut.

AutoIt , 333 byte

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

Kode uji sampel:

ConsoleWrite(l("atoll", "bowl") & @LF)
ConsoleWrite(l("tar", "tarp") & @LF)
ConsoleWrite(l("turing", "tarpit") & @LF)
ConsoleWrite(l("antidisestablishmentarianism", "bulb") & @LF)

hasil panen

3
1
4
27

k4, 66 byte

{$[~#x;#y;~#y;#x;&/.z.s'[-1 0 -1_\:x;0 -1 -1_\:y]+1 1,~(*|x)=*|y]}

Sebuah algo yang membosankan dan pada dasarnya tidak digubah. 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

Serius, 86 82 78 byte

,#,#`k;;;░="+l"£@"│d);)[]oq╜Riu)@d);)@[]oq╜Riu(@)@)@[]oq╜Ri3}@)=Y+km"£@IRi`;╗ƒ

Hex Dump:

2c232c23606b3b3b3bb03d222b6c229c4022b364293b295b5d6f71bd526975294064293b29405b
5d6f71bd5269752840294029405b5d6f71bd5269337d40293d592b6b6d229c40495269603bbb9f

Cobalah secara Online

(Perhatikan bahwa tautannya ke versi yang berbeda karena sesuatu tentang penerjemah online terputus dengan versi baru yang lebih pendek, meskipun itu berfungsi dengan baik dengan penerjemah yang dapat diunduh.)

Ini tentang implementasi yang paling mudah. ​​Serius memungkinkan untuk definisi rekursif. Ini sangat lambat karena tidak ada memoisasi sama sekali. Mungkin metode tabular bisa lebih pendek (mungkin dengan menggunakan register sebagai baris), tapi saya cukup senang dengan ini, terlepas dari seberapa banyak kekurangan-kekurangan yang saya temukan. Yang itu bisa digunakan

[]oq`<code>`Ri

sebagai panggilan fungsi dua argumen yang tepat adalah penemuan yang bagus.

Penjelasan:

,#,#                             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

Python 3, 267 216 184 162 byte

Fungsi ini menghitung jarak Levenshtein menggunakan array yang 2 x len(word_2)+1berukuran.

Sunting: Ini tidak mendekati jawaban Python 2 Willem, tapi di sini ada jawaban yang lebih golf dengan banyak perbaikan kecil di sana-sini.

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]

Tidak Disatukan:

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]

Retina , 78 72 byte

&`(.)*$(?<!(?=((?<-4>\4)|(?<-1>.(?<-4>)?))*,(?(4),))^.*,((.)|(?<-1>.))*)

Cobalah online!

Di satu sisi, ini adalah solusi regex murni di mana hasilnya adalah jumlah posisi yang cocok dengan regex. Karena kenapa tidak ...

Peringatan yang adil, ini sangat tidak efisien. Cara kerjanya adalah bahwa ia menurunkan optimasi yang sebenarnya ke backtracker mesin regex, yang dengan sederhana memaksa semua penyelarasan yang mungkin, mulai dengan perubahan sesedikit mungkin dan memungkinkan satu lagi sampai memungkinkan untuk mencocokkan string dengan penambahan, penghapusan dan penggantian. .

Untuk solusi yang sedikit lebih masuk akal, yang satu ini hanya cocok sekali dan tidak memiliki pencarian negatif. Di sini, hasilnya adalah jumlah tangkapan dalam grup 2, yang dapat Anda akses dengan match.Groups[2].Captures.Countdi C #, misalnya. Ini masih sangat tidak efisien.

Penjelasan

Saya menjelaskan versi kedua di atas, karena secara konseptual sedikit lebih mudah (karena itu hanya satu pertandingan regex). Ini adalah versi yang tidak di-serigala yang saya beri nama grup (atau membuat mereka tidak menangkap) dan menambahkan komentar. Ingat bahwa komponen dalam tampilan harus dibaca dari belakang ke depan, tetapi alternatif dan tampilan di dalam itu harus dibaca dari depan ke belakang. Ya.

.+                      # 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.
  )*
)

Satu-satunya perbedaan pada versi 72-byte adalah bahwa kita dapat melepaskan yang terdepan .+(dan grup kedua di awal) dengan menemukan posisi di akhir di mana kita tidak memiliki cukup <ops>dan menghitung semua posisi itu.

Haskell , 67 64 byte

e@(a:r)#f@(b:s)=sum[1|a/=b]+minimum[r#f,e#s,r#s]
x#y=length$x++y

Cobalah online! Contoh penggunaan: "turing" # "tarpit"hasil 4.

Penjelasan (untuk versi 67 byte sebelumnya)

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

Ini adalah solusi rekursif. Diberikan dua string edan f, pertama-tama kita membandingkan karakter pertama adan b. Jika mereka sama, maka jarak Levenshtein edan fsama dengan jarak Levenshtein rdan s, sisa edan fsetelah menghapus karakter pertama. Kalau tidak, salah satu aatau bperlu dihapus, atau satu diganti dengan yang lain. [r#f,e#s,r#s]secara rekursif menghitung Levenshtein untuk ketiga kasus tersebut, minimummengambil yang terkecil, dan 1ditambahkan ke akun untuk operasi pemindahan atau penggantian yang diperlukan.

Jika salah satu senarnya kosong, kita naik ke baris kedua. Dalam hal ini, jaraknya hanya panjang dari string yang tidak kosong, atau setara dengan panjang dari kedua string yang disatukan.

Python 3 , 105 94 93 byte

-11 byte oleh 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)

Versi golf dari implementasi tersingkat di Wikibooks .

Cobalah online!

Haskell, 136 byte

Panggil e. Agak lambat antidisestablishmentarianismdll.

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 byte

Coba di sini!

~LiI
~L   calculate the Levenshtein distance of
  i   input string
   I  and another input string

Saya menambahkan bahwa builtin kemarin, tetapi melihat tantangan ini hari ini, yaitu, baru saja. Namun, jawaban ini tidak bersaing.

Dalam versi yang lebih baru:

~Li

mengambil input kedua implisit.

GNU Prolog, 133 byte

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);!).

Mengambil tuple sebagai argumen. Contoh penggunaan:

| ?- l("turing"-"tarpit",D).

D = 4

yes

mMenentukan bahwa Badalah Abaik secara langsung maupun dengan karakter pertama dihapus. dkegunaan msebagai sebuah sub rutin untuk menghitung suatu mengedit jarak antara unsur-unsur tuple (yaitu jarak dari serangkaian suntingan yang mengubah satu ke yang lain). Kemudian ladalah trik standar untuk menemukan minimum d(Anda mengambil jarak sewenang-wenang, kemudian mengambil jarak lebih kecil sewenang-wenang, ulangi sampai Anda tidak bisa pergi lebih kecil).

Perl, 168 166 163 byte

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)

Implementasi rekursif. Simpan di file.pldan jalankan sebagai 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)

• perbarui 166 : abaikan ()dalam panggilan l.
• pembaruan 163 : hilangkan returndengan menyalahgunakan dodalam trinary.

APL (Dyalog Classic) , 34 byte

{⊃⌽⊖¯1(⊢⌊(1+⌽⌊⊖)⌊⍵+⊣⌽⊖)⍣≡+\+⍀⍵}∘.≠

Cobalah online!

C, 192 byte

#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;}
---------

Terperinci

#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 #, 215 210 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;}

lebih mudah dibaca:

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]

Saya akhirnya membuat ini untuk memecahkan tantangan lain yang melibatkan LD.

Penjelasan kode dengan komentar.

# 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|%{
    # Save the column index for use in the next pipeline
    $i=$_

    # Working the rows.
    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]

JavaScript (ES6),  95 91  89 byte

Mengambil input sebagai (source)(target). Pada dasarnya sebuah port jawaban @ Willem's Python (kemudian dioptimalkan oleh @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)

Cobalah online!