Problem 93. Calculate the Levenshtein distance between two strings

Created by Cody Team

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This problem description is lifted from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Levenshtein_distance\"><w:r><w:t>http://en.wikipedia.org/wiki/Levenshtein_distance</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example, the Levenshtein distance between \"kitten\" and \"sitting\" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ kitten => sitten  (substitution of 's' for 'k')\n sitten => sittin  (substitution of 'e' for 'i')\n sittin => sitting (insert 'g' at the end).]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So when</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s1 = 'kitten']]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>and</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s2 = 'sitting']]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then the distance d is equal to 3.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

1063 Solutions
570 Solvers

Last Solution submitted on Sep 12, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

jj L on 9 Aug 2018

Good question

Stephan Allgeier on 10 Jan 2020

I really like this problem. So far, this is the one I had to think about most. Mostly because the straight-forward recursive implementation is simply not feasible for longer inputs.

Solution Comments

Solution 616393

1 Comment

1 Comment

bainhome on 10 Apr 2018

Shameless code... now i'll do that in right way.

Solution 216928

1 Comment

1 Comment

Marco Castelli on 13 Mar 2013

The simplest solution for beginner, now I'm trying to solve in a correct way

Solution 214056

3 Comments

3 Comments

Nicholas Howe on 11 Mar 2013

Apparently the test suite needs to be augmented!

Ned Gulley on 12 Mar 2013

Done. People never get tired of look-up tables.

David Verrelli on 21 Apr 2018

Indeed: all of the current supposedly 'top ten' submissions here (by Cody-size) are hard-coded hacks! The Test Suite can be augmented by: (i) adding more arbitrary test cases; (ii) adding test cases in which the first [and last] characters/words are the same as in some other test case(s); (iii) banning mention of numbers that correspond to results and need not be mentioned in legitimate submissions (e.g. 18, 25, 27) [as implemented for Problem 44466]; and (iv) potentially banning other key words appearing in other 'generic' hacks (per Solutions 312146 and 1039520). —DIV

Problem Recent Solvers570

Problem Tags

matlab string metric

Problem 93. Calculate the Levenshtein distance between two strings

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers570

Suggested Problems

More from this Author95

Problem Tags

Problem 93. Calculate the Levenshtein distance between two strings

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers570

Suggested Problems

More from this Author95

Problem Tags

Players