龙空技术网

「面试必备」最长公共子序列算法

Wgrape 114

前言:

此刻咱们对“最长公共子序列 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 #求最长公共子字符串 #动态规划算法实现最长公共子序列问题 #动态规划算法求最长公共子序列 #用动态规划算法求解最长公共子序列