MediumNLPnlp-031

Levenshtein Edit Distance

Problem

Return the Levenshtein edit distance between two strings using unit costs for insertion, deletion, and substitution.

An empty source needs len(target) insertions, and identical strings have distance 0.

Hint

Fill an (n + 1) x (m + 1) table, where each cell adds one edit on top of a neighbor.

case 1

in: ["kitten","sitting"]

expected: 3

case 2

in: ["","abc"]

expected: 3

case 3

in: ["abc","abc"]

expected: 0

case 4

in: ["flaw","lawn"]

expected: 2

case 5

in: ["",""]

expected: 0

Starter codePython

def levenshtein(s1, s2):
    # Your code here
    pass

5 test cases · run your code against them in the editor