basic Dart's Levenshtein distance.

levenshtein.dart

import 'dart:math' as math;

/// see https://en.wikipedia.org/wiki/Levenshtein_distance
void main() {
  /// terms distance can be used as threshold value when you filter similar results.
  /// if the number of "editions" is low, you can suppose a typo and provide the "similar"
  /// result (maybe using the `int` distance as a sorting method).
  print(levenshtein('sittin', 'sitting'));
  print(levenshtein('casa', 'calle'));
}

int levenshtein(String term1, String term2) {
  if (term1.isEmpty || term2.isEmpty) return 0;
  final m = term1.length + 1;
  final n = term2.length + 1;
  final tmp = List.filled(n - 1, 0);
  final d = List.generate(
    m,
    (i) => (i == 0) ? List.generate(n, (j) => j) : [i, ...tmp],
  );
  for (var i = 1; i < m; ++i) {
    for (var j = 1; j < n; ++j) {
      final cost = (term1[i - 1] == term2[j - 1]) ? 0 : 1;
      d[i][j] = math.min(
        math.min(d[i - 1][j] + 1, d[i][j - 1] + 1),
        d[i - 1][j - 1] + cost,
      );
    }
  }
  return d[m - 1][n - 1];
}