Problem 848. Calculate a modified Levenshtein distance between two strings

Created by Matthew Eicholtz

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>Inspired by the Cody problem found</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\"><w:r><w:t>here</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 is a charater-based string metric used to measure the difference between two strings (for details, look</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>here</w:t></w:r></w:hyperlink><w:r><w:t>). In this problem, you need to implement a word-based version of the Levenshtein distance.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given two strings, compute the minimum number of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>word</w:t></w:r><w:r><w:t>-edits to transform one string into another. The allowable edits are insertion, deletion, or substitution of a single</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>word</w:t></w:r><w:r><w:t>. Assume words are case-insensitive. Contractions and hyphenated words are allowed, but you may ignore other punctuation.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[s1 = 'I do not like MATLAB'\ns2 = 'I love MATLAB a lot']]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[d = 4]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>because at least four edits are required to transform s1 into s2 (substitution on the last four words).</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>"}]}

Inspired by the Cody problem found <a href="http://www.mathworks.com/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings">here</a>.The Levenshtein distance is a charater-based string metric used to measure the difference between two strings (for details, look <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">here</a>). In this problem, you need to implement a word-based version of the Levenshtein distance.Given two strings, compute the minimum number of word-edits to transform one string into another. The allowable edits are insertion, deletion, or substitution of a single word. Assume words are case-insensitive. Contractions and hyphenated words are allowed, but you may ignore other punctuation.ExampleIf<pre class="language-matlab">s1 = 'I do not like MATLAB'
s2 = 'I love MATLAB a lot'
</pre>then<pre class="language-matlab">d = 4
</pre>because at least four edits are required to transform s1 into s2 (substitution on the last four words).

Solve

Solution Stats

198 Solutions
53 Solvers

Last Solution submitted on Dec 26, 2020

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

Richard Zapor on 20 Jul 2012

Question on Test Suite #2.
s1 = 'Which words need to be edited?';
s2 = 'Can you tell which words need to be edited?';
d_correct = 3;
I see this as a 2, Substitute w for W and insert 'Can you tell ' - done. Where is the 3rd change?

Matthew Eicholtz on 20 Jul 2012

Richard - you do not have to substitute w for W (words are case-insensitive). And inserting 'Can you tell' is three edits, one for each word.

Rafael S.T. Vieira on 26 Aug 2020

I understand how this problem was designed, but I disagree. For instance transforming s1 = 'I do not like MATLAB' into s2 = 'I love MATLAB a lot' should be a 2-word edit, because the 3-words 'do not like' could be grouped into 1-word and changed into 'love', as well as 'a lot' could be treated as just 1-word insertion after the word MATLAB. And that's probably how the original Leveshtein distance would measure it, since the algorithm returns 15-character edits: transforming 'do not like' into 'love' requires 9-character edits, and inserting ' a lot' after 'MATLAB' requires 6-character edits.

Solution Comments

Solution 1225109

1 Comment

1 Comment

Informaton on 20 Aug 2017

Was the problem too difficult; unclear?

Solution 116435

1 Comment

1 Comment

Tim on 20 Jul 2012

With regexp assistance from 115643.

Problem Recent Solvers53

Problem Tags

string metric strings

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 848. Calculate a modified Levenshtein distance between two strings

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers53

Suggested Problems

More from this Author44

Problem Tags

Community Treasure Hunt

Problem 848. Calculate a modified Levenshtein distance between two strings

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers53

Suggested Problems

More from this Author44

Problem Tags

Community Treasure Hunt

Players