一、概念

假设存在如下两个字符串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

感谢阅读，欢迎关注博客

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