HardNLPnlp-032

Damerau Input with Adjacent Transposition

Problem

Return the optimal string alignment distance between two strings: like Levenshtein, but swapping two adjacent characters costs 1 edit.

This is the restricted 'lite' Damerau variant, so an adjacent transposition followed by further edits can cost more than the unrestricted distance. Identical strings have distance 0.

Hint

Add a fourth candidate to the usual three using the cell at (i - 2, j - 2).

Test cases

case 1

in: ["ab","ba"]

expected: 1

case 2

in: ["ca","abc"]

expected: 3

case 3

in: ["teh","the"]

expected: 1

case 4

in: ["abc","abc"]

expected: 0

case 5

in: ["","ab"]

expected: 2

Starter codePython

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

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