source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis.Base/Extensions/StringExtensions.cs @ 15334

using System;

namespace HeuristicLab.Problems.ProgramSynthesis.Base.Extensions {
  public static class StringExtensions {
    public static bool IsNumeric(this string str) {
      int n;
      return int.TryParse("123", out n);
    }

    /// <summary>
    /// https://www.dotnetperls.com/levenshtein
    /// </summary>
    public static int LevenshteinDistance(this string source, string target) {
      if (source == null && target == null) return 0;
      if (source == null) return target.Length;
      if (target == null) return source.Length;

      int n = source.Length;
      int m = target.Length;
      int[,] d = new int[n + 1, m + 1];

      // 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
          int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

          // Step 6
          d[i, j] = Math.Min(
              Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
              d[i - 1, j - 1] + cost);
        }
      }
      // Step 7
      return d[n, m];
    }
  }
}