Levenshtein Distance

Showcases multidimensional arrays and string metric calculations. This example demonstrates the allocation of a 2D integer array ('new Integer[slen + 1, tlen + 1]') and the use of 'MinInt' for dynamic programming calculations.

Source Code

function LevenshteinDistance(s, t : String) : Integer;
begin
  var slen := Length(s);
  var tlen := Length(t);
  var d := new Integer[slen + 1, tlen + 1];

  for var i := 0 to slen do d[i, 0] := i;
  for var j := 0 to tlen do d[0, j] := j;

  for var j := 1 to tlen do begin
    for var i := 1 to slen do begin
      if s[i] = t[j] then
        d[i, j] := d[i-1, j-1]
      else begin
        d[i, j] := MinInt(
          MinInt(d[i-1, j] + 1, d[i, j-1] + 1),
          d[i-1, j-1] + 1
        );
      end;
    end;
  end;
  Result := d[slen, tlen];
end;
PrintLn('Distance between "kitten" and "sitting": ' + IntToStr(LevenshteinDistance('kitten', 'sitting')));

Result

Distance between "kitten" and "sitting": 3

← Towers of Hanoi Maze Generation →