wordsLevenshteinDistance function

int wordsLevenshteinDistance(String word1, String word2)

Implementation

int wordsLevenshteinDistance(String word1, String word2) {
  final m = word1.length + 1;
  final n = word2.length + 1;

  final matrix = List.generate(m, (_) => List<int>.filled(n, 0));

  for (var i = 0; i < m; i++) {
    matrix[i][0] = i;
  }

  for (var j = 0; j < n; j++) {
    matrix[0][j] = j;
  }

  for (var i = 1; i < m; i++) {
    for (var j = 1; j < n; j++) {
      final cost = word1[i - 1] == word2[j - 1] ? 0 : 1;
      matrix[i][j] = [
        matrix[i - 1][j] + 1,
        matrix[i][j - 1] + 1,
        matrix[i - 1][j - 1] + cost
      ].reduce(min);
    }
  }

  return matrix[m - 1][n - 1];
}