levenshteinDistance function

int levenshteinDistance(String s1, String s2)

Calculates the Levenshtein distance between two strings.

The Levenshtein distance is a metric that measures the difference between two strings. It is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one string into the other.

This function takes two strings s1 and s2 and returns the Levenshtein distance between them.

Implementation

int levenshteinDistance(final String s1, final String s2) {
  if (s1 == s2) {
    return 0;
  }
  if (s1.isEmpty) {
    return s2.length;
  }
  if (s2.isEmpty) {
    return s1.length;
  }

  List<int> v0 = List<int>.generate(s2.length + 1, (i) => i);
  List<int> v1 = List<int>.filled(s2.length + 1, 0);

  for (int i = 0; i < s1.length; i++) {
    v1[0] = i + 1;

    for (int j = 0; j < s2.length; j++) {
      int cost = (s1[i] == s2[j]) ? 0 : 1;
      v1[j + 1] = min(v1[j] + 1, min(v0[j + 1] + 1, v0[j] + cost));
    }

    for (int j = 0; j < v0.length; j++) {
      v0[j] = v1[j];
    }
  }

  return v1[s2.length];
}