editDistance function

int editDistance(String a, String b)

Levenshtein (edit) distance between a and b.

Identifiers are case-sensitive; distance ≤ 2 counts as "similar" for typo-candidate search. Classic single-row DP, no external dependencies.

Implementation

int editDistance(String a, String b) {
  if (a == b) return 0;
  if (a.isEmpty) return b.length;
  if (b.isEmpty) return a.length;

  final rows = List<int>.generate(b.length + 1, (j) => j);
  for (var i = 1; i <= a.length; i++) {
    var prev = rows[0];
    rows[0] = i;
    for (var j = 1; j <= b.length; j++) {
      final tmp = rows[j];
      rows[j] = a.codeUnitAt(i - 1) == b.codeUnitAt(j - 1)
          ? prev
          : 1 + _min3(rows[j], rows[j - 1], prev);
      prev = tmp;
    }
  }
  return rows[b.length];
}