文章内容更新请以 WGrape GitHub博客 : 图解最长公共子序列算法 为准
前言
本文原创，著作权归WGrape所有，未经授权，严禁转载
一、概念
假设存在如下两个字符串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);
}
}
