Levenshtein distance is one of my favorite algorithms. On the surface it seems so very simple, but when you spend some time thinking hard on it deep insights are waiting to be had. The first and most important thing about Levenshtein distance is it’s actually a metric distance. That is, it obeys the triangle inequality. [...]