前言:
此刻咱们对“最长公共子序列 leetcode”大体比较关切,姐妹们都想要学习一些“最长公共子序列 leetcode”的相关内容。那么小编在网上收集了一些关于“最长公共子序列 leetcode””的相关内容,希望姐妹们能喜欢,咱们一起来了解一下吧!一、概念
假设存在如下两个字符串A和B,对两个字符串中公有的字符高亮标注
A的高亮子序列 = [e]、[o]、[e,o]、[o,o]、[e,o,o]B的高亮子序列 = [e]、[o]、[e,o]、[e,e]、[o,e]、[o,e,e]、[e,o,e]、[e,e,e]、[e,o,e,e]
其中[e,o]是两个字符串公有的最长高亮子序列
把经过计算后得到的两个字符串公有的最长高亮子序列,称为最长公共子序列(LCS)
二、动态规划解法
解决最长公共子序列问题可以使用动态规划算法,动态规划的核心是以下两个步骤
1、子问题
先找到最长公共子序列的子问题,即截止到字符串A的第i个字符和截止到字符串B的第j个字符的最长公共子序列,把它记为result[i][j]
2、状态转移方程
(1) 当 i = 0 或 j = 0 时,result[i][j] = 0
(2) 当 A[i] = B[j] 时,result[i][j] = result[i-1][j-1] + 1
(3) 当 A[i] ≠ B[j] 时,result[i][j] = max(result[i-1][j], result[i][j-1])
三、算法过程1、画出表格
假设字符串A=niceto,字符串B=hellowo,可以得到一个7*8的表格,其中i和j分别是字符串A和B的下标
2、循环表格
对得到的7*8的表格循环遍历,并根据状态转移方程,在表格中写入计算后的数字
(1) i=0
根据状态方程(1)中规定,第一次循环时,写入的所有数字都是0,如下所示
(2) i=1~3
当i=1,2,3时,每次循环判断都没有相同的字符,所以根据状态方程(3)规定,写入的所有数字都是0,如下所示
(3) i=4
当i=4时,发现在j=2的情况下,A[i] = B[j] = e,根据状态方程(2)的规定,在result[4][2]中填入1后,又根据状态方程(3)的规定,在其之后的单元格中也都填入1
(4) i=5
当i=5时,同样的也根据状态方程(3)的规定,填入如下数字
(5) i=6
当i=6时,发现在j=5,7的情况下,都出现了A[i]=B[j]的情况,所以写入数字如下
3、找出最大值
循环表格之后,表格中的每个单元都填入了数字,找到最大值等于2,所以字符串A和B的LCS就是2
4、伪代码
function computeLCS(){ let length1 = A.length; let length2 = B.length; let result; let max = 0 for(let i=0; i<=length1; i++){ for(let j=0; j<=length2; j++){ if(i===0 || j===0){ result[i][j] = 0; continue; } if(A[i] === B[j]){ result[i][j] = result[i-1][j-1] + 1; }else{ result[i][j] = max(result[i-1][j], result[i][j-1]); } max = Math.max(max, result[i][j]); } } return max;}四、例题讲解1、两个字符串的删除操作(1) 题目介绍
给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符(来自《LeetCode第583题》)
(2) 解题思路
从题目介绍和给出的示例中可以看出来,本题可以先转化为求两个字符串的最长公共子序列LCS,再计算两个字符串的长度分别减去LCS的之和,得到的数字就是最小步数
(3) 实现代码
class Solution { /** * @param String $word1 * @param String $word2 * @return Integer */ function minDistance($word1, $word2) { $result = []; $length1 = strlen($word1); $length2 = strlen($word2); $max = 0; for($i=0;$i<=$length1;++$i){ for($j=0;$j<=$length2;++$j){ if($i === 0 || $j === 0){ $result[$i][$j] = 0; continue; } if($word1[$i-1] === $word2[$j-1]){ $result[$i][$j] = $result[$i-1][$j-1] + 1; }else{ $result[$i][$j] = max($result[$i-1][$j], $result[$i][$j-1]); } $max = max($max, $result[$i][$j]); } } return ($length1-$max) + ($length2-$max); }}五、结束
对于最长公共子串问题,可以使用相同的解法,只是状态转移方程会有如下差别
(1) 当 i = 0 或 j = 0 时,result[i][j] = 0
(2) 当 A[i] = B[j] 时,result[i][j] = result[i-1][j-1] + 1
(3) 当 A[i] ≠ B[j] 时,result[i][j] = 0
感谢阅读,欢迎关注博客
标签: #最长公共子序列 leetcode #求最长公共子字符串 #动态规划算法实现最长公共子序列问题 #动态规划算法求最长公共子序列 #用动态规划算法求解最长公共子序列