Skip to content

Instantly share code, notes, and snippets.

@remi-bruguier
Created May 29, 2020 20:09
Show Gist options
  • Save remi-bruguier/cc08c3a8bfa5129e76f745ae3af0fecb to your computer and use it in GitHub Desktop.
Save remi-bruguier/cc08c3a8bfa5129e76f745ae3af0fecb to your computer and use it in GitHub Desktop.
Given two strings, determine the edit distance between them. The edit distance is defined as the minimum number of edits (insertion, deletion, or substitution) needed to change one string to the other.
const getEditDistance = function(a: string, b: string):number{
if(!a.length) return b.length;
if(!b.length) return a.length;
const matrix:number[][] = [];
// fill first row and column
for(let i = 0; i <= b.length; i++){
matrix[i] = [i];
}
for(let j = 0; j <= a.length; j++){
matrix[0][j] = j;
}
// fill the rest of the matrix
for(let i = 1; i <= b.length; i++){
for(let j = 1; j <= a.length; j++){
// different char, calculate min
if(b[i-1] != a[j-1]){
matrix[i][j] = Math.min(matrix[i-1][j-1] + 1,matrix[i][j-1] + 1, matrix[i-1][j] + 1);
// same char, no operation, use previous min value
} else {
matrix[i][j] = matrix[i-1][j-1];
}
}
}
return matrix[b.length][a.length];
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment