levenshtein.hpp File Reference

#include <algorithm>
#include <string>
#include <vector>

Go to the source code of this file.

Functions
auto	levenshteinDistance (const std::string &s1, const std::string &s2) -> size_t
	Computes the Levenshtein distance between two strings.

Function Documentation

levenshteinDistance()

auto levenshteinDistance	(	const std::string &	s1,
		const std::string &	s2 ) -> size_t

Computes the Levenshtein distance between two strings.

The Levenshtein distance is calculated by finding the minimum number of operations required to transform one string into another. The allowed operations are:

• Insertion: Insert a character into one string.
• Deletion: Delete a character from one string.
• Substitution: Replace a character in one string with another.

Parameters

s1	The first string.
s2	The second string.

Returns

The Levenshtein distance between the two strings.

This implementation uses dynamic programming to compute the Levenshtein distance. A 2D table is constructed, where each entry at [i][j] contains the distance between the first i characters of s1 and the first j characters of s2. The final distance is found at the bottom-right corner of the table. The time complexity of this algorithm is O(m * n), where m and n are the lengths of the two input strings.

< Length of the first string.

< Length of the second string.

< Cost of deleting characters from s1 to match empty s2.

< Cost of inserting characters into s1 to match s2.

< Deletion

< Insertion

< Substitution