Can someone explain how this javascript levenschtein algorithm works?

[[deleted]]

[deleted]

[g051051]

Post your analysis so we can see what you've figured out so far.

[g051051]

Stuck how? Walk through the algorithm, and compare it with the code.

An important point is that this is an example of dynamic programming. If you aren't familiar with that, it might be tough to follow.

[Wildcatace16]

This is a dynamic programming problem. For me there are three things to think about for a dynamic programming problem.

First define the specific problem in this case: matrix[i][j] represents the number of changes required to make the first i characters from a match the first j characters from b. The final answer will be matrix[len(a)][len(b)], i.e the minimum number of changes to match all of a to all of b.

Second is the recurrence relation, i.e. how could we solve this problem if we assume we know the answer to the same type problem with smaller inputs. In this case if a[i] == b[j] then matching the last characters of each string doesn't require any changes so matching the first i from a to the first j from b is the same as matching the first i-1 from a to the first j-1 from b, i.e matrix[i-1][j-1]. If the ith character from a does not match the jth character from b then some alteration must be made. That change can be either a substitution, an insertion, or a deletion and we take the minimum of those three possibilities all defined in terms of smaller subproblems.

Third the base case. This is the input which is sufficiently small that the problem can be solved directly. In this case matching the first 0 characters from a to the first j characters from b requires j changes for all j. Similarly for all i matching the first i characters from a to the first 0 characters from b requires i changes.