Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
72 lines (60 sloc) 2.05 KB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SEA2016.FuzzySearch
{
/// <summary>
/// Calculate Levenshtein distance between two strings using brute-force recursive algorithm
/// https://en.wikipedia.org/wiki/Levenshtein_distance#Recursive
/// </summary>
public static class LevenshteinBruteForce
{
public static int Calculate(string a, string b)
{
return CalculateRecursive(a, b, a.Length, b.Length);
}
private static int CalculateRecursive(string a, string b, int m, int n)
{
if (Math.Min(m, n) == 0)
{
return Math.Max(m, n);
}
var subCost = ((a[m - 1] == b[n - 1]) ? 0 : 1) + CalculateRecursive(a, b, m - 1, n - 1);
var delCost = 1 + CalculateRecursive(a, b, m, n - 1);
var insCost = 1 + CalculateRecursive(a, b, m - 1, n);
return Math.Min(subCost, Math.Min(insCost, delCost));
}
private static int Calculate2(string a, string b, int m, int n)
{
if (b.Length == n)
{
return (a.Length - m);
}
if (a.Length == m)
{
return (b.Length - n);
}
if (a[m] == b[n])
{
return Calculate2(a, b, m + 1, n + 1);
}
else
{
var subCost = Calculate2(a, b, m + 1, n + 1);
var delCost = Calculate2(a, b, m + 1, n);
var insCost = Calculate2(a, b, m, n + 1);
return 1 + Math.Min(subCost, Math.Min(insCost, delCost));
}
}
}
public static class Program
{
public static void Main(string[] args)
{
var words = Console.ReadLine().Split(' ');
Console.WriteLine($"Distance between words {words[0]} and {words[1]} using brute-force algorithm:");
Console.WriteLine(LevenshteinBruteForce.Calculate(words[0], words[1]));
}
}
}