damerauLevenshteinDistance<E> function

int damerauLevenshteinDistance<E>(
  1. List<E> source,
  2. List<E> target
)

Finds the Damerau–Levenshtein distance between two lists which allows deletion, insertion, substitution and transposition using Wagner–Fischer algorithm

Parameters

  • source and target are two list of items.

Details

Edit distance is a way to quantify how dissimilar two list of items are to one another by counting minimum number of single-index operations required to transform one list to the other.

This variation of edit distance algorithm allows 4 types of operations:

  • insertions: insert a single item anywhere in the source list
  • deletions: delete a single item from the source
  • substitutions: replace one item with another in the source
  • transposition: swap two adjacent items in the source

This functions returns the minimum number of these operations required to transform source into target without modifying their contents.

If n is the length of source, m is the length of target, and k is the number of unique items appearing on the lists,
Complexity: Time O(nm log k) | Space O(nm + k)

Implementation

int damerauLevenshteinDistance<E>(List<E> source, List<E> target) {
  return damerauLevenshteinDistanceDefault(source, target);
}