Skip to content

Instantly share code, notes, and snippets.

@savaged
Last active October 5, 2022 07:13
Show Gist options
  • Select an option

  • Save savaged/20e40486df410f6a15b26805dd8b363a to your computer and use it in GitHub Desktop.

Select an option

Save savaged/20e40486df410f6a15b26805dd8b363a to your computer and use it in GitHub Desktop.
Recursive version of Levenshtein distance algorithm
namespace savaged.RecursionFun
{
/// <summary>
/// See https://programm.top/en/c-sharp/algorithm/levenshtein-distance/
/// </summary>
public static class RecursiveLevenshteinDistance
{
public static int Distance(string value1, string value2) =>
Distance(value1, value1?.Length ?? 0, value2, value2?.Length ?? 0);
private static int Distance(string value1, int len1, string value2, int len2)
{
if (string.IsNullOrEmpty(value1)) return len2;
if (string.IsNullOrEmpty(value2)) return len1;
if (len1 == 0) return len2;
if (len2 == 0) return len1;
var substitutionCost = 0;
if (value1[len1 - 1] != value2[len2 - 1])
{
substitutionCost = 1;
}
var deletion = Distance(value1, len1 - 1, value2, len2) + 1;
var insertion = Distance(value1, len1, value2, len2 - 1) + 1;
var substitution = Distance(value1, len1 - 1, value2, len2 - 1) + substitutionCost;
return Minimum(deletion, insertion, substitution);
}
private static int Minimum(int a, int b, int c) => (a = a < b ? a : b) < c ? a : c;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment