Solves
similarity
Articles
STR
Algorithm
Edit distance
The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it.
O(m · n)
2 problems
STR
Data structure
BK-tree
All passwords one or two edits from a given one: the triangle inequality cuts off whole branches, and where it stops helping.
O(N · depth) to build
1 problem
Problems
Often together
dynamic programming 1 matrix 1 search engines 1 bioinformatics 1 diffing 1 classic 1 interviews 1 nearest neighbour 1 tree 1 security 1 string matching 1