This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* This is a simple and performant implementation of | |
* the Wagner–Fischer algorithm for computing | |
* the Levenshtein Distance between two strings. | |
* | |
* It is based on the observation that we can reserve a matrix | |
* to hold the Levenshtein distances between all prefixes of | |
* the first string and all prefixes of the second. | |
* | |
* Then we can compute the values in the matrix |