levenshteinDistance function

int levenshteinDistance(String s1, String s2)

Calculates the Levenshtein distance between two strings

Implementation

int levenshteinDistance(String s1, String s2) {
  if (s1.isEmpty) return s2.length;
  if (s2.isEmpty) return s1.length;

  final matrix = List<List<int>>.generate(
    s1.length + 1,
    (i) => List<int>.generate(s2.length + 1, (j) => 0),
  );

  // Initialize first row and column
  for (var i = 0; i <= s1.length; i++) {
    matrix[i][0] = i;
  }
  for (var j = 0; j <= s2.length; j++) {
    matrix[0][j] = j;
  }

  // Fill in the rest of the matrix
  for (var i = 0; i < s1.length; i++) {
    for (var j = 0; j < s2.length; j++) {
      if (s1[i] == s2[j]) {
        matrix[i + 1][j + 1] = matrix[i][j];
      } else {
        matrix[i + 1][j + 1] = min(
          min(matrix[i][j + 1] + 1, matrix[i + 1][j] + 1),
          matrix[i][j] + 1,
        );
      }
    }
  }

  return matrix[s1.length][s2.length];
}