for ($i = 0; $i < $l2; $i++) {
for ($j = 0; $j < $l1; $j++) {
if ($s2[$i] == $s1[$j]) {
$a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1] + 1, $a[$i + 1][$j] + 1);
}else{
$a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1], $a[$i + 1][$j]) + 1;
}
}
}

echo $a[$l1][$l2];
echo "n";
echo levenshtein($s1, $s2);

在 PHP 的实现中，实现者在注释中很清楚的标明：此函数仅优化了内存使用，而没有考
虑速度，从其实现算法看，时间复杂度为 O(m×n)。其优化点在于将上面的状态转移方程
中的二维数组变成了两个一组数组。简单实现如下：

 

复制代码 代码如下:

<?PHP
$s1 = "abcjfdkslfdd";
$l1 = strlen($s1);
$s2 = "aab84093840932bd";
$l2 = strlen($s2);

$dis = 0;
for ($i = 0; $i <= $l2; $i++){
$p1[$i] = $i;
}

for ($i = 0; $i < $l1; $i++){
$p2[0] = $p1[0] + 1;

for ($j = 0; $j < $l2; $j++){
if ($s1[$i] == $s2[$j]){
$dis = min($p1[$j], $p1[$j + 1] + 1, $p2[$j] + 1);
}else{
$dis = min($p1[$j] + 1, $p1[$j + 1] + 1, $p2[$j] + 1); // 注意这里最后一个参数
为$p2 
}
$p2[$j + 1] = $dis;