72.md

✏️基础刷题之(72. Edit Distance)

. 2019-05-27 吴亲库里 库里的深夜食堂

✏️描述

给定两个字符串暂且称之为a，b,让我们求把字符串a变成字符串b至少需要几步操作，操作的动作分别是delete，insert，replace，并且每个操作只能操作一个字符串。

---

✏️题目实例

​

---

✏️题目分析

还是那两个步骤，状态的定义以及递推公式。分两种情况，如果他们相等，当前的替换数就等于之前的替换数，否则直接比较前增，删，改的替换数最小值作为当前最小替换数。

DP[$i][$j] //表示把word1前i个字符串替换成word2前j个字符串的最少步数

  if(substr($word,$i-1,1)==substr($word,$j-1,1)
  DP[$i][$j]=DP[$i-1][$j-1];
  else
  DP[$i][$j]=min(DP[$i-1][$j],DP[$i][$j-1],DP[$i-1][$j-1])+1;  

✏️最终实现代码

   /**
        * @param String $word1
        * @param String $word2
        * @return Integer
        */
       function minDistance($word1, $word2) {
       
           for($i=0;$i<=strlen($word1);$i++) $dp[$i][0]=$i;
           for($i=0;$i<=strlen($word2);$i++) $dp[0][$i]=$i;      
           
           for($i=1;$i<=strlen($word1);$i++){
               for($j=1;$j<=strlen($word2);$j++){
                   if(substr($word1,$i-1,1)==substr($word2,$j-1,1)){
                       $dp[$i][$j]=$dp[$i-1][$j-1];
                   }else{
                       $dp[$i][$j]=min($dp[$i-1][$j],$dp[$i][$j-1],$dp[$i-1][$j-1])+1;
                   }
               }
           }
           return $dp[strlen($word1)][strlen($word2)];
       }

---

联系

​