LevenshteinStringMetric.cs

#define ENABLE_CACHE

namespace Levenshtein;

public static class LevenshteinStringMetric
{
#if ENABLE_CACHE
    public static int MeasureStringDistance(string source, string target) => LevImpl(source, target, new Dictionary<(int, int), int>());
    
    private static int LevImpl(string a, string b, Dictionary<(int, int), int> cache)
    {
        if (cache.TryGetValue((a.Length, b.Length), out var distance))
            return distance;

        if (a.Length is 0)
        {
            cache.TryAdd((a.Length, b.Length), b.Length);
            return b.Length;
        }

        if (b.Length is 0)
        {
            cache.TryAdd((a.Length, b.Length), a.Length);
            return a.Length;
        }
        
        distance = a[0] == b[0]
            ? LevImpl(a[1..], b[1..], cache)
            : 1 + Min(LevImpl(a[1..], b, cache), LevImpl(a, b[1..], cache),
                LevImpl(a[1..], b[1..], cache));
        cache.TryAdd((a.Length, b.Length), distance);
        return distance;
    }
#else
    public static int MeasureStringDistance(string a, string b)
    {
        while (true)
        {
            if (a.Length is 0) return b.Length;
            if (b.Length is 0) return a.Length;
            if (a[0] != b[0]) return 1 + Min(MeasureStringDistance(a[1..], b), MeasureStringDistance(a, b[1..]), MeasureStringDistance(a[1..], b[1..]));
            a = a[1..];
            b = b[1..];
        }
    }
#endif

    private static int Min(int x, int y, int z)
    {
        if (x < y && x < z)
            return x;
        
        if (y < x && y < z)
            return y;
        
        return z;
    }
}