restrictedDamerauDistanceOf function

int restrictedDamerauDistanceOf(
  1. String source,
  2. String target, {
  3. bool ignoreCase = false,
  4. bool ignoreWhitespace = false,
  5. bool ignoreNumbers = false,
  6. bool alphaNumericOnly = false,
})

Finds the restricted Damerau-Levenshtein edit distance between two strings 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

The restricted edit distance or optimal string alignment distance or computes the number of edit operations needed to make two strings equal under the condition that no substring is edited more than once.

This is a variation of Damerau-Levenshtein distance implemented by damerauLevenshteinDistance. It restricts the transposition operation so that the operation is only applied to unedited portion of the source, not after changing it once.

For example, CA can be transformed into ABC in 2 steps using Damerau-Levenshtein method: CA -> AC -> ABC

But under the above mentioned condition, after CA -> AC, the substring AC can not be further modified. So, it requires 3 steps here: CA -> AA -> AB -> ABC

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 and m is the length of target,
Complexity: Time O(nm) | Space O(3m)

Implementation

int restrictedDamerauDistanceOf(
  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 restrictedDamerauDistanceDefault(source.codeUnits, target.codeUnits);
}