Levenshtein Distance

Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. It is named after Vladimir Levenshtein, who considered this distance in 1965.

• C#
• VB.Net
• C
• C++
• PHP

									private static uint MIN3(uint a, uint b, uint c)
{
	return ((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c)));
}

public static int LevenshteinDistance(string s1, string s2)
{
	uint s1len, s2len, x, y, lastdiag, olddiag;
	s1len = (uint)s1.Length;
	s2len = (uint)s2.Length;
	uint[] column = new uint[s1len + 1];

	for (y = 1; y <= s1len; ++y)
		column[y] = y;

	for (x = 1; x <= s2len; ++x)
	{
		column[0] = x;

		for (y = 1, lastdiag = x - 1; y <= s1len; ++y)
		{
			olddiag = column[y];
			column[y] = MIN3(column[y] + 1, column[y - 1] + 1, (uint)(lastdiag + (s1[(int)(y - 1)] == s2[(int)(x - 1)] ? 0 : 1)));
			lastdiag = olddiag;
		}
	}

	return (int)(column[s1len]);
}
								

Example

									int result = LevenshteinDistance("kitten", "sitting");
								

Output

									result: 3