例如將kitten一字轉成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄羅斯科學家Vladimir Levenshtein在1965年提出這個概念。
套用
DNA分析
拼字檢查
語音辨識
抄襲偵測
算法
動態規劃經常被用來作為這個問題的解決手段之一。
整數 Levenshtein距離(字元串 str1[1..m], 字元串 str2[1..n])
//聲明變數， d[i , j]用於記錄str1[1...i]與str2[1..j]的Levenshtein距離
int d[0..m, 0..n]
//初始化
for i from 0 to m
d[i, 0] := i
for j from 0 to n
d[0, j] := j
//用動態規劃方法計算Levenshtein距離
for i from 1 to m
for j from 1 to n
{
//計算替換操作的代價，如果兩個字元相同，則替換操作代價為0，否則為1
if str1[i]== str2[j] then cost := 0
else cost := 1
//d[i,j]的Levenshtein距離，可以有
d[i, j] := minimum(
d[i-1, j] + 1, //在str2上j位置刪除字元（或者在str1上i-1位置插入字元）
d[i, j-1] + 1, //在str2上j-1位置插入字元（或者在str1上i位置刪除字元）
d[i-1, j-1] + cost // 替換操作
)
}
//返回d[m, n]
return d[m, n]
wikisource上有不同的程式語言的版本。
pascal代碼
procedure levenshtein;
var
st1,st2:string;
d:array[0..1000000] of integer;
i,j,m,n,cost:integer;
begin
m:=length(st1);
n:=length(st2);
for i:=0 to m do
d[i,0]:=i;
for j:= 0 to n do
d[0,j]:=j;
for i:= 1 to m do
for j:= 1 to n do
begin
if st1[i]=st2[j] then
cost:=0
else cost:=1;
if cost=0 then
begin
if (d[i-1,j]<d[i,j-1]) and (d[i-1,j]+1<d[i-1,j-1]+cost)
then d[i,j]:=d[i-1,j]+1
else if d[i,j-1]+1< d[i-1,j-1]+cost
then d[i,j]:=d[i,j-1]+1
else d[i,j]:=d[i-1,j-1]+cost;
end;
end;
