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

栏目: 编程工具 · 发布时间: 5年前

内容简介:动态规划题系列最后一题

2 0 1 9 -5 -26   期天    

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

动态规划题系列最后一题

Leetcode动态规划之 <a href='https://www.codercto.com/topics/18749.html'>PHP</a> 解析(72. Edit Distance)

题目描述

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

题目解析

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

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

/**
     * @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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C++Templates中文版

C++Templates中文版

David Vandevoorde、Nicolai M.Josuttis / 陈伟柱 / 人民邮电出版社 / 2008-2 / 69.00元

本书是C++模板编程的完全指南,旨在通过基本概念、常用技巧和应用实例3方面的有用资料,为读者打下C++模板知识的坚实基础。 全书共22章。第1章全面介绍了本书的内容结构和相关情况。第1部分(第2~7章)以教程的风格介绍了模板的基本概念,第2部分(第8~13章)阐述了模板的语言细节,第3部分(第14~18章)介绍了C++模板所支持的基本设计技术,第4部分(第19~22章)深入探讨了各种使用模板......一起来看看 《C++Templates中文版》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具