damerauLevenshteinDistanceOf function

int damerauLevenshteinDistanceOf(String source, String target, { bool ignoreCase = false, bool ignoreWhitespace = false, bool ignoreNumbers = false, bool alphaNumericOnly = false, })

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

Parameters

• source and target are two strings.
• if ignoreCase is true, the character case shall be ignored.
• if ignoreWhitespace is true, space, tab, newlines etc whitespace characters will be ignored.
• if ignoreNumbers is true, numbers will be ignored.
• if alphaNumericOnly is true, only letters and digits will be matched.

TIPS: You can pass both ignoreNumbers and alphaNumericOnly to true to ignore everything else except letters.

Details

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

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

• insertions: insert a single character anywhere in the source
• deletions: delete a single character from the source
• substitutions: replace one character with another in the source
• transposition: swap two adjacent characters 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 characters appearing on the string,
Complexity: Time O(nm log k) | Space O(nm + k)

Implementation

int damerauLevenshteinDistanceOf(
  String source,
  String target, {
  bool ignoreCase = false,
  bool ignoreWhitespace = false,
  bool ignoreNumbers = false,
  bool alphaNumericOnly = false,
}) {
  source = cleanupString(
    source,
    ignoreCase: ignoreCase,
    ignoreWhitespace: ignoreWhitespace,
    ignoreNumbers: ignoreNumbers,
    alphaNumericOnly: alphaNumericOnly,
  );
  target = cleanupString(
    target,
    ignoreCase: ignoreCase,
    ignoreWhitespace: ignoreWhitespace,
    ignoreNumbers: ignoreNumbers,
    alphaNumericOnly: alphaNumericOnly,
  );
  return damerauLevenshteinDistanceDefault(source.codeUnits, target.codeUnits);
}