Console.WriteLine(LevenshteinDistanceRecursive("book", "barf"));
Console.WriteLine(LevenshteinDistanceIterative("aaaa", ""));
public static int LevenshteinDistanceRecursive<T, GetA, GetB, Equals>(
where GetA : IFunc<int, T>
where GetB : IFunc<int, T>
where Equals : IFunc<T, T, bool>
throw new ArgumentOutOfRangeException(nameof(a_length), a_length, $@"{nameof(a_length)} < 0");
throw new ArgumentOutOfRangeException(nameof(b_length), b_length, $@"{nameof(b_length)} < 0");
int Do(int ai, int bi) =>
bi >= b_length ? 1 + Do(ai + 1, bi) :
equals.Do(a.Do(ai), b.Do(bi)) ? Do(ai + 1, bi + 1) :
1 + Min(Do(ai, bi + 1), Do(ai + 1, bi), Do(ai + 1, bi + 1));
public static int Min(int a, int b, int c) => Math.Min(Math.Min(a, b), c);
public static int LevenshteinDistanceRecursive(string a, string b) =>
LevenshteinDistanceRecursive<char, GetIndexString, GetIndexString, EqualsChar>(
a: a, a_length: a.Length,
b: b, b_length: b.Length);
public struct GetIndexString : IGetIndex<char>
public char Do(int index) => String[index];
public static implicit operator GetIndexString(string @string) =>
new GetIndexString() { String = @string, };
public struct EqualsChar : IEquate<char>
public bool Do(char a, char b) => a == b;
public static int LevenshteinDistanceIterative(string a, string b) =>
LevenshteinDistanceIterative<char, GetIndexString, GetIndexString, EqualsChar>(
a: a, a_length: a.Length,
b: b, b_length: b.Length);
public static int LevenshteinDistanceIterative<T, GetA, GetB, Equals>(
where GetA : IFunc<int, T>
where GetB : IFunc<int, T>
where Equals : IFunc<T, T, bool>
throw new ArgumentOutOfRangeException(nameof(a_length), a_length, $@"{nameof(a_length)} < 0");
throw new ArgumentOutOfRangeException(nameof(b_length), b_length, $@"{nameof(b_length)} < 0");
int[,] matrix = new int[a_length, b_length];
for (int i = 1; i < a_length; i++)
for (int i = 1; i < b_length; i++)
for (int bi = 1; bi < b_length; bi++)
for (int ai = 1; ai < a_length; ai++)
!equals.Do(a.Do(ai - 1), b.Do(bi - 1)) ? matrix[ai - 1, bi - 1] + 1 : matrix[ai - 1, bi - 1]);
return matrix[a_length - 1, b_length - 1];