内容简介:动态规划题系列最后一题
2 0 1 9 -5 -26 星 期天 开 始 吧
这周四周五有事情没有更新
动态规划题系列最后一题
题目描述
给定两个字符串暂且称之为a,b,让我们求把字符串a变成字符串b至少需要几步操作,操作的动作分别是delete,insert,replace,并且每个操作只能操作一个字符串。
题目解析
还是那两个步骤,状态的定义以及递推公式。分两种情况,如果他们相等,当前的替换数就等于之前的替换数,否则直接比较前增,删,改的替换数最小值作为当前最小替换数。
/** * @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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode动态规划之PHP解析(120. Triangle)
- 解析 :跻身数据科学领域的五条职业规划道路
- Leetcode动态规划之PHP解析(70. Climbing Stairs)
- Leetcode动态规划之PHP解析(152. Maximum Product Subarray)
- Leetcode动态规划之PHP解析(300. Longest Increasing Subsequence)
- Leetcode动态规划之PHP解析(123. Best Time to Buy and Sell Stock III)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Data Structures and Algorithms with JavaScript
Michael McMillan / O'Reilly Media / 2014-2-22 / USD 28.51
If you’re using JavaScript on the server-side, you need to implement classic data structures that conventional object-oriented programs (such as C# and Java) provide. This practical book shows you how......一起来看看 《Data Structures and Algorithms with JavaScript》 这本书的介绍吧!