title: Levenshtein Distance Algorithm: C# Implementation

by Lasse Johansen

public class Distance {
/// <summary>
/// Compute Levenshtein distance
/// </summary>
/// <param name="s">String 1</param>
/// <param name="t">String 2</param>
/// <returns>Distance between the two strings.
/// The larger the number, the bigger the difference.
/// </returns>
  public int LD (string s, string t) {
  int n = s.Length; //length of s
  int m = t.Length; //length of t
  int[,] d = new int[n + 1, m + 1]; // matrix
  int cost; // cost
    // Step 1
    if(n == 0) return m;
    if(m == 0) return n;
    // Step 2
    for(int i = 0; i <= n; d[i, 0] = i++);
    for(int j = 0; j <= m; d[0, j] = j++);
    // Step 3
    for(int i = 1; i <= n;i++) {
      //Step 4
      for(int j = 1; j <= m;j++) {
        // Step 5
        cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);
        // Step 6
        d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
      }
    }
    // Step 7
    return d[n, m];
  }
}