算法：子串、子序列相关问题小结
引言
在动态规划当中，有一类问题十分的相似，甚至用的方法都大差不差；
没错，那就是子串和子序列，他们的核心都是通过建立一个二维数组记录当前匹配的长度；只要掌握了这个精髓，那么其它相似的题目也就都迎刃而解啦！????????
注：若初始化矩阵出现了问题，可以看看鄙人的这边文章->别看了 别看了，都是浅拷贝惹的祸
子串问题
相关题目1：最长重复子数组
718. 最长重复子数组
题目描述：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。 复制代码
构建一个二维数组：dp[A.length+1][B.length+1]
状态转移方程为：
当A[i] == B[j] 那么dp[i][j] = dp[i - 1][j - 1] + 1 (在图上就是左上方斜着+1)
当A[i] != B[j] 那么dp[i][j] = 0
所以，从题目当中，可得如图矩阵（这里建议直接动手画画，会更清楚）
那么，代码如下
var findLength = function(nums1, nums2) { let res = 0; let m = nums1.length; let n = nums2.length; const dp = new Array(m + 1) // 1. for(let i = 0; i <= m; i++){ dp[i] = new Array(n + 1).fill(0) } for(let i = 1; i<=m;i++){ //2. for(let j = 0; j<=n ;j++){ if(nums1[i-1] === nums2[j-1]){ //3. dp[i][j] = dp[i - 1][j - 1] + 1 res = Math.max(res,dp[i][j]) } } } return res }; 复制代码代码解释：
这里初始化矩阵的长度和宽度分别是
m + 1，n + 1的原因是把矩阵的第一行和第一列作为初始化状态，都设为0；（若这里的初始化矩阵出现了问题，可以看看鄙人的这边文章->别看了 别看了，都是浅拷贝惹的祸 ）遍历都从1开始的原因是，我们已经将第一行和第一列作为初始化状态了，因此都从1开始遍历
这里需要注意就是，i和j对应数组当中的index都是大于1的，所以对比的时候-1
相关题目2：最长公共子串
最长公共子串
题目描述：给定两个字符串str1和str2,输出两个字符串的最长公共子串
输入："1AB2345CD","12345EF" 返回值："2345" 复制代码
这里和前面不同的是，需要我们输入所匹配的公共子串，而不是长度；
那么类似地，我们依然可以用上面的方法；只不过，我们最后需要保存下来当前的i或者j的值，这样我们就可以通过公共子串的长度和i（或j）对传入的字符串进行截取，就可以得到我们需要的啦！
代码如下：
function LCS( str1 , str2 ) { const dp = new Array(str1.length + 1); let max = 0; const map = new Map() //采用map的形式进行存贮索引值 for (let i = 0; i <= str1.length; i++) { // 初始化整个dp矩阵，每个值为0 dp[i] = new Array(str2.length + 1).fill(0); } for(let i = 1;i<=str1.length;i++){ for(let j = 1;j<=str2.length;j++){ if(str1[i-1] === str2[j-1]){ dp[i][j] = dp[i - 1][j - 1] + 1 max = Math.max(max,dp[i][j]) if(!map.has(max)) map.set(max,i) //避免重复,也就是只有当max这个值改变的时候，我们才会对对应的索引进行存贮 } } } let startIndex = map.get(max) - max; let endIndex = map.get(max) ; return str1.substring(startIndex,endIndex) //截取字符串 } 复制代码子序列问题
首先，我们要知道，子串和子序列最大的区别就是，子序列可以是不连续；而子串必须是连续的；
知道了这一点之后，来看题目->go!????♀️
相关题目1：最长公共子序列
1143. 最长公共子序列
题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。 复制代码
同样也是构建二维数组的思路；但是这里我们需要注意的是，状态方程发生了变化
状态转移方程为：
当A[i] == B[j] 那么dp[i][j] = dp[i - 1][j - 1] + 1 (在图上就是左上方斜着+1)
当A[i] != B[j] 那么dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1])(在图上就是上方或左边的最大值)
这里，可以自己再画画图（鄙人懒????????）
代码如下：
var longestCommonSubsequence = function(text1, text2) { let res = 0; if(text1.length === 0 || text2.length === 0) return 0; let m = text1.length; let n = text2.length; const dp = new Array(m + 1); for(let i = 0; i<=m ;i++){ dp[i] = new Array(n + 1).fill(0) } for(let i = 1; i<=m ;i++){ for(let j = 1; j <= n;j++){ if(text1[i - 1] === text2[j-1]){ dp[i][j] = dp[i-1][j-1] + 1 }else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) } res = Math.max(res,dp[i][j]) } } return res }; 复制代码相关题目2：两个字符串的删除操作
583. 两个字符串的删除操作
这道题和上面那题题简直就是一模一样，用我们的小脑袋瓜想想，这本质上也是在找公共的子序列，所以就解释那么多了，直接上代码：
var minDistance = function(text1, text2) { let res = 0; if(text1.length === 0 || text2.length === 0) return 0; let m = text1.length; let n = text2.length; const dp = new Array(m + 1); for(let i = 0; i<=m ;i++){ dp[i] = new Array(n + 1).fill(0) } for(let i = 1; i<=m ;i++){ for(let j = 1; j <= n;j++){ if(text1[i - 1] === text2[j-1]){ dp[i][j] = dp[i-1][j-1] + 1 }else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) } res = Math.max(res,dp[i][j]) } } return m + n - 2*res //唯一的不同就是处理一下返回值 }; 复制代码看起来相似，但其实又没什么关系的题目
题目1： 最长公共前缀
14. 最长公共前缀
var longestCommonPrefix = function(strs) { if(strs.length === 0) return ''; if(strs.length === 1) return strs[0]; strs.sort() //排序就将差别最大的放在了第一个和最后一个 let start = strs[0]; let end = strs[strs.length - 1]; let len = start.length < end.length ? start.length : end.length; let result = ''; for(let i = 0; i < len; i++){ //所以这里只需要对比第一个和最后一个就可以了 if(start[i]!==end[i]) break result += start[i] } return result }; 复制代码题目2：判断是不是子字符串
判断是不是子字符串
const s = readline() let t = readline() let flag = true for (let i = 0; i< s.length;i++){ if(t.indexOf(s[i]) === -1){ flag = false console.log(false) break; }else{ t = t.slice(t.indexOf(s[i]) + 1) } } if(flag) console.log(true) 复制代码...
嘿哈！后续题目还在继续整理中…
作者：乐嫣
链接：https://juejin.cn/post/7015178783808290829