| 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[0] = 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 extends num>(T a, T b, T c) { |

| return min(min(a, b), c); |

| } |