実行例
kitten => sitting : 3
Saturday => Sunday : 3
 => foo : 3
にほんご => にっぽんご : 2

以下、C#とVBでの実装。 最適化はしていない。

using System;

class Sample {
  private static int Min(int x, int y, int z)
  {
    return Math.Min(Math.Min(x, y), z);
  }

  private static int ComputeLevenshteinDistance(string strX, string strY)
  {
    if (strX == null)
      throw new ArgumentNullException("strX");
    if (strY == null)
      throw new ArgumentNullException("strY");

    if (strX.Length == 0)
      return strY.Length;
    if (strY.Length == 0)
      return strX.Length;

    var d = new int[strX.Length + 1, strY.Length + 1];

    for (var i = 0; i <= strX.Length; i++) {
      d[i, 0] = i;
    }

    for (var j = 0; j <= strY.Length; j++) {
      d[0, j] = j;
    }

    for (var j = 1; j <= strY.Length; j++) {
      for (var i = 1; i <= strX.Length; i++) {
        if (strX[i - 1] == strY[j - 1])
          d[i, j] = d[i - 1, j - 1];
        else
          d[i, j] = Min(d[i - 1, j] + 1,
                        d[i, j - 1] + 1,
                        d[i - 1, j - 1] + 1);
      }
    }

    return d[strX.Length, strY.Length];
  }

  static void Main()
  {
    foreach (var texts in new[] {
      new[] {"kitten", "sitting"},
      new[] {"Saturday", "Sunday"},
      new[] {"", "foo"},
      new[] {"にほんご", "にっぽんご"},
    }) {
      Console.WriteLine("{0} => {1} : {2}",
                        texts[0],
                        texts[1],
                        ComputeLevenshteinDistance(texts[0], texts[1]));
    }
  }
}