Damerau-Levenshtein Distance (OSA)
HardDynamic ProgrammingString
Description
Return the Optimal String Alignment (OSA) distance between two strings: minimum edits using insertion, deletion, substitution, and transposition of two adjacent characters, with the restriction that no substring is edited more than once (the common DP formulation).
Examples
Input:
a = "abcd", b = "acbd"Output:
1Explanation:
Strings differ by adjacent swap of 'b' and 'c', costing one transposition.
Input:
a = "abc", b = "abc"Output:
0Explanation:
The strings are identical so no edits are needed; the distance is 0.
Input:
a = "", b = "abc"Output:
3Explanation:
Three insertions of 'a', 'b', 'c' transform the empty string into 'abc', giving distance 3.
Constraints
- •
0 ≤ a.length, b.length ≤ 100