## 如何在Delphi中实现Levenshtein距离？内容来源于 Stack Overflow，并遵循CC BY-SA 3.0许可协议进行翻译与使用

• 回答 (1)
• 关注 (0)
• 查看 (51)

### 1 个回答

```function EditDistance(s, t: string): integer;
var
d : array of array of integer;
i,j,cost : integer;
begin
{
Compute the edit-distance between two strings.
Algorithm and description may be found at either of these two links:
http://en.wikipedia.org/wiki/Levenshtein_distance
}

//initialize our cost array
SetLength(d,Length(s)+1);
for i := Low(d) to High(d) do begin
SetLength(d[i],Length(t)+1);
end;

for i := Low(d) to High(d) do begin
d[i,0] := i;
for j := Low(d[i]) to High(d[i]) do begin
d[0,j] := j;
end;
end;

//store our costs in a 2-d grid
for i := Low(d)+1 to High(d) do begin
for j := Low(d[i])+1 to High(d[i]) do begin
if s[i] = t[j] then begin
cost := 0;
end
else begin
cost := 1;
end;

//to use "Min", add "Math" to your uses clause!
d[i,j] := Min(Min(
d[i-1,j]+1,      //deletion
d[i,j-1]+1),     //insertion
d[i-1,j-1]+cost  //substitution
);
end;  //for j
end;  //for i

//now that we've stored the costs, return the final one
Result := d[Length(s),Length(t)];

//dynamic arrays are reference counted.
//no need to deallocate them
end;```