levenshtein.hpp

Go to the documentation of this file.

#pragma once
 
#include <algorithm>
#include <string>
#include <vector>


auto levenshteinDistance(const std::string& s1, const std::string& s2) -> size_t
{
  size_t len1 = s1.size(); 
  size_t len2 = s2.size(); 
 
  // 2D table to store the distances between substrings of s1 and s2.
  std::vector<std::vector<size_t>> dist(len1 + 1, std::vector<size_t>(len2 + 1));
 
  // Initialize the first column and row of the table.
  for (size_t i = 0; i <= len1; ++i)
    dist[i][0] = i; 
 
  for (size_t j = 0; j <= len2; ++j)
    dist[0][j] = j; 
 
  // Fill the rest of the table with the calculated distances.
  for (size_t i = 1; i <= len1; ++i)
  {
    for (size_t j = 1; j <= len2; ++j)
    {
      // If the characters at the current positions are the same, no cost to substitute.
      size_t cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
 
      // Calculate the minimum of deletion, insertion, or substitution operations.
      dist[i][j] = std::min({
        dist[i - 1][j] + 1,       
        dist[i][j - 1] + 1,       
        dist[i - 1][j - 1] + cost 
      });
    }
  }
 
  // Return the computed Levenshtein distance, which is the value at the bottom-right corner of the
  // table.
  return dist[len1][len2];
}