Question

How to calculate Levenshtein distance between two strings (min chars to transform str1 into str2) in C++

Answer 1

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // std::min

/*
The Levenshtein distance = the minimal number of characters you have to 
replace, insert or delete to transform string1 into string2. 
*/

// Compute Levenshtein distance between two strings
int levenshtein(const std::string& s1, const std::string& s2) {
    size_t len1 = s1.size();
    size_t len2 = s2.size();

    std::vector<std::vector<int>> dp(len1 + 1, std::vector<int>(len2 + 1));

    for (size_t i = 0; i <= len1; i++) dp[i][0] = static_cast<int>(i);
    for (size_t j = 0; j <= len2; j++) dp[0][j] = static_cast<int>(j);

    for (size_t i = 1; i <= len1; i++) {
        for (size_t j = 1; j <= len2; j++) {
            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
            dp[i][j] = std::min({
                dp[i - 1][j] + 1,       // deletion
                dp[i][j - 1] + 1,       // insertion
                dp[i - 1][j - 1] + cost // substitution
            });
        }
    }
    
    return dp[len1][len2];
}

// Find the closest word from a list
std::string findClosestWord(const std::string& input, const std::vector<std::string>& words) {
    int shortest_dis = -1;
    std::string closest_w;

    for (const auto& word : words) {
        int dis = levenshtein(input, word);

        if (dis == 0) {
            return word; // exact match
        }

        if (dis <= shortest_dis || shortest_dis < 0) {
            closest_w = word;
            shortest_dis = dis;
        }
    }
    return closest_w;
}

int main() {
    std::string s = "PHHP";
    std::vector<std::string> arr = {"C", "PHP", "C++", "Java", "C#", "JavaScript"};

    std::string closest_w = findClosestWord(s, arr);

    std::cout << "word: " << s << "\n";
    if (closest_w == s) {
        std::cout << "Exact match found: " << closest_w << "\n";
    } else {
        std::cout << "Did you mean: " << closest_w << "?\n";
    }
}


/*
run:

word: PHHP
Did you mean: PHP?

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // std::min

/*
The Levenshtein distance = the minimal number of characters you have to 
replace, insert or delete to transform string1 into string2. 
*/

#include <iostream>
#include <string>
#include <vector>

// Compute Levenshtein distance between two strings
int levenshtein(const std::string& s1, const std::string& s2) {
    const size_t len1 = s1.size();
    const size_t len2 = s2.size();

    // DP table: (len1+1) x (len2+1)
    std::vector<std::vector<int>> dp(len1 + 1, std::vector<int>(len2 + 1));

    // Base cases
    for (size_t i = 0; i <= len1; ++i) dp[i][0] = static_cast<int>(i);
    for (size_t j = 0; j <= len2; ++j) dp[0][j] = static_cast<int>(j);

    // Fill table
    for (size_t i = 1; i <= len1; i++) {
        for (size_t j = 1; j <= len2; j++) {
            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
            dp[i][j] = std::min({
                dp[i - 1][j] + 1,       // deletion
                dp[i][j - 1] + 1,       // insertion
                dp[i - 1][j - 1] + cost // substitution
            });
        }
    }

    return dp[len1][len2];
}

int main() {
    std::string str1 = "kitten";
    std::string str2 = "sitting";

    int distance = levenshtein(str1, str2);

    std::cout << "Levenshtein distance between \"" 
              << str1 << "\" and \"" << str2 
              << "\" is " << distance << "\n";
}


/*
run:

Levenshtein distance between "kitten" and "sitting" is 3

*/

 

70+ SQL courses for beginners and professionals