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];

  }

}