blob: 6ee7359cd1478a24ba84b105d23866a910bdadff [file] [log] [blame]
 import 'dart:math'; /// Calculates Levenshtein distance between [s] and [t]. /// /// The Levenshtein distance is defined as the minimum number of edit operations /// required to convert [s] to [t]. An edit operation can either be: /// /// 1. Inserting a character /// 2. Deleting a character /// 3. Substituting a character. /// /// This implementation is case-sensitive. int levenshteinDistance(String s, String t) { ArgumentError.checkNotNull(s, 's'); ArgumentError.checkNotNull(t, 't'); /// Swap the strings if necessary so we can reduce the space requirement. final a = s.length > t.length ? s : t; final b = s.length > t.length ? t : s; /// Levenshtein Distance can be computed by creating a matrix such that /// `distances[i][j]` holds the edit distance to convert from the first i /// letters of [s] to the first j letters of [t], and dynamically computing /// upwards. We reduce the space requirement by repeatedly updating just /// one row. final distances = List.filled(b.length + 1, 0); /// Initialize the first row. for (var j = 0; j < distances.length; j++) { distances[j] = j; } for (var i = 1; i <= a.length; i++) { distances = i; /// Holds the value of `distances[i-1][j-1]` if we had been using a mtraix. var holder = i - 1; for (var j = 1; j <= b.length; j++) { final newDistance = _min3( 1 + distances[j], // Deletion 1 + distances[j - 1], // Insertion // Substitution holder + (a.codeUnitAt(i - 1) == b.codeUnitAt(j - 1) ? 0 : 1)); holder = distances[j]; distances[j] = newDistance; } } return distances[b.length]; } /// Utility function to calculate the minimum of [a], [b], and [c]. T _min3(T a, T b, T c) { return min(min(a, b), c); }