HardNLPnlp-346

Edit Distance Substitution Cost Two

Problem

Compute the Levenshtein-style edit distance where insertion and deletion cost 1 but substitution costs 2, using dynamic programming over prefixes.

Given the two strings, return the distance.

Hint

Mismatched characters cost 2 when substituted, versus 2 for delete plus insert.

case 1

in: ["cat","cot"]

expected: 2

case 2

in: ["kitten","sitting"]

expected: 5

case 3

in: ["abc","abc"]

expected: 0

Starter codePython

def edit_distance_substitution_cost_two(a, b):
    # Your code here
    pass

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