[面试必备]最长公共子序列算法

一、概念

假设存在如下两个字符串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]是两个字符串公有的最长高亮子序列

image.png

把经过计算后得到的两个字符串公有的最长高亮子序列,称为最长公共子序列(LCS)

image.png

二、动态规划解法

解决最长公共子序列问题可以使用动态规划算法,动态规划的核心是以下两个步骤

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的下标

image.png

2、循环表格

对得到的7*8的表格循环遍历,并根据状态转移方程,在表格中写入计算后的数字

(1) i=0

根据状态方程(1)中规定,第一次循环时,写入的所有数字都是0,如下所示
image.png

(2) i=1~3

当i=1,2,3时,每次循环判断都没有相同的字符,所以根据状态方程(3)规定,写入的所有数字都是0,如下所示
image.png

(3) i=4

当i=4时,发现在j=2的情况下,A[i] = B[j] = e,根据状态方程(2)的规定,在result[4][2]中填入1后,又根据状态方程(3)的规定,在其之后的单元格中也都填入1
image.png

(4) i=5

当i=5时,同样的也根据状态方程(3)的规定,填入如下数字
image.png

(5) i=6

当i=6时,发现在j=5,7的情况下,都出现了A[i]=B[j]的情况,所以写入数字如下
image.png

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题》)
image.png

(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

感谢阅读,欢迎关注博客

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 1

题目有点没看懂。。我记得有道题最长公共子串是用滑动窗口来做的,好像跟这道题没什么关联?

2年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!