Leetcode动态规划之PHP解析(72. Edit Distance)


2019-5-26 期天  


这周四周五有事情没有更新

动态规划题系列最后一题


019f47bff32b657fe60ba2534122e41e.png

题目描述

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


题目解析

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

335a1d2712e430b6250275bf7f53a7a4.png

 /**
     * @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)];
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D71 788. Rotated Digits

>> 下一篇: Leetcode PHP题解--D72 349. Intersection of Two Arrays