Problem 848. Calculate a modified Levenshtein distance between two strings

Inspired by the Cody problem found here.

The Levenshtein distance is a charater-based string metric used to measure the difference between two strings (for details, look here). 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.

Example

s1 = 'I do not like MATLAB'
s2 = 'I love MATLAB a lot'

then

d = 4

because at least four edits are required to transform s1 into s2 (substitution on the last four words).

Problem Group

Community

Solve This Now!

4 solvers submitted 10 solutions (2.5 solutions/solver).

Solution Map Solution List Solvers

Problem Comments

2 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?

Matt 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.

Problem 848. Calculate a modified Levenshtein distance between two strings

Tags

Problem Group

4 solvers submitted 10 solutions (2.5 solutions/solver).

Problem Comments

Solution Comments