给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。 你可以对一个单词执行以下3种操作： a）在单词中插入一个字符 b）删除单词中的一个字符 c）替换单词中的一个字符
<?php /** * @param $word1 * @param $word2 * @return mixed * $arrStep[$j][$i]代表了第一个字符串的前i个字符构成第二个字符串前j个字符的最小步数 * 规律是 当word1的第i个字符==word2的第j个字符时,那么$arrStep[$j][$i] = $arrStep[$j-1][$i-1] * 意思是前i-1构成前j-1个的步数,多了第i和第j两个字符,步数不发生变化 * 当word1的第i个字符!==word2的第j个字符时,那么$arrStep[$j][$i] = min($arrStep[$j - 1][$i - 1] + 1, $arrStep[$j - 1][$i] + 1, $arrStep[$j][$i - 1] + 1) * 意思是前i-1构成前j-1个的步数、前i构成j-1的步数 和前i-1构成j的步数 中最小的步数,然后+1 */ function minDistance($word1, $word2) { $num1 = strlen($word1); $num2 = strlen($word2); $arrStep = array(); //空位补的第一行所需要的步数 for ($i = 0; $i <= $num1; $i ++) { $arrStep[0][$i] = $i; } //空位补的第一列所需要的步数 for ($i = 0; $i <= $num2; $i ++) { $arrStep[$i][0] = $i; } for ($j = 1; $j <= $num2; $j ++) { for ($i = 1; $i <= $num1; $i ++) { if ($word1[$i - 1] == $word2[$j - 1]) { $arrStep[$j][$i] = $arrStep[$j - 1][$i - 1]; } else { $arrStep[$j][$i] = min($arrStep[$j - 1][$i - 1] + 1, $arrStep[$j - 1][$i] + 1, $arrStep[$j][$i - 1] + 1); } } } return $arrStep[$num2][$num1]; } $a = 'bcd'; $b = 'abde'; $ret = minDistance($a, $b); print $ret;
