Levenshtein distance

levenshtein_distance.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int levenshtein_distance(const string &str_a, const string &str_b)
{
    if (str_a.empty())
        return str_b.length();

    if (str_b.empty())
        return str_a.length();

    if (str_a[0] == str_b[0])
        return levenshtein_distance(str_a.substr(1), str_b.substr(1));

    return 1 + min({
                   levenshtein_distance(str_a.substr(1), str_b),
                   levenshtein_distance(str_a, str_b.substr(1)),
                   levenshtein_distance(str_a.substr(1), str_b.substr(1)),
               });
}

int main()
{
    cout << levenshtein_distance("kitten", "sitten") << endl; // 1
    cout << levenshtein_distance("sittin", "sitting") << endl; // 1

    cout << levenshtein_distance("a", "b") << endl; // 1
    cout << levenshtein_distance("a", "bc") << endl; // 2
    cout << levenshtein_distance("abc", "def") << endl; // 3
    cout << levenshtein_distance("abcdef", "def") << endl; // 3
    cout << levenshtein_distance("abc", "abcdef") << endl; // 3
    cout << levenshtein_distance("abc", "xyz") << endl; // 3
}