indelDistance function

int indelDistance(String s1, String s2)

Calculates the InDel distance (Insertion-Deletion distance) between two strings

Implementation

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

  // InDel distance is equivalent to Levenshtein where substitution cost is infinity
  // Since we can't represent infinity, we just make it higher than any possible distance
  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;
  }

  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(
          matrix[i][j + 1] + 1, // deletion
          matrix[i + 1][j] + 1, // insertion
        );
      }
    }
  }

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