levenshteinDistanceOf function

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

Finds the Levenshtein distance between two strings which allows deletion, insertion and substitution 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.

The Levenshtein distance allows three types of operations on a string:

  • insertions: insert a single character anywhere in the string
  • deletions: delete a single character from the string
  • substitutions: replace one character with another in a string

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

This function also provides a multitude of ways to customize the distance. You can choose to ignore cases, whitespaces, numbers, or non-alphanumeric characters when calculating the distance.

If n is the length of source and m is the length of target,
Complexity: Time O(nm) | Space O(n)

Implementation

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