js substring、js substring和substr 收藏 0

NOC青少儿编程大赛Python复赛真题解析-最长的回文子串[解析]

给你一个字符串s，找到s中最长的回文子串。

“如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。”

输入：s = \”babad\”

输出：\”bab\”

中心扩展算法

思路：回文字符串有两种类型，比如 aba 或者 abbc。

第一种是一个中心点往两边扩展；

第二种是两个中心点往两边扩展；

遍历中心点，使用双指针往两边扩展，如果两边的字母相同，就可以继续扩展；如果两边的字母不同，就停止扩展，取两种情况的最大子串

参考程序（kidscode.cn）：

如果有兴趣可以尝试动态规划的方法，仅提供思路。

动态规划

思路：使用动态规划算法解题步骤

定义状态：

我们可以定义 dp[i][j] 表示从索引 i 到 j 的子串是否为回文串。

初始化状态：

将所有长度为 1 的子串都初始化为回文，即 dp[i][i] = true。

检查所有长度为 2 的子串，如果两个字符相等，将 dp[i][i+1] 设为 true。

状态转移方程：

对于长度大于 2 的子串，dp[i][j] 是否为回文串取决于 dp[i+1][j-1] 和 s[i] == s[j]。

即dp[i][j] = dp[i+1][j-1] && s[i] == s[j]。

处理边界条件：

在上述初始化中已经处理了长度为 1 和 2 的情况。

自底向上构建解：

通过两层嵌套循环，自底向上地填充 dp 数组，从小规模子问题逐步构建到整个问题。

记录最优解：

在状态转移的过程中，不断更新记录最长回文子串的起始索引和长度。

返回结果：

最终，通过起始索引和长度，可以得到最长回文子串

原文少儿编程网（kidscode.cn）

LeetCode5.2-动态规划求解最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = \”babad\”

输出：\”bab\”

解释：\”aba\” 同样是符合题意的答案。

示例 2：

输入：s = \”cbbd\”

输出：\”bb\”

示例 3：

输入：s = \”a\”

输出：\”a\”

示例 4：

输入：s = \”ac\”

输出：\”a\”

前边两篇文章分别使用中心扩展法、马拉车算法求解了最长回文子串，本文用动态规划解一下此题。不得不说动态规划解决此问题也是一个时间复杂度为O(n^2)的算法，只是通过这个问题感受一下动态规划的解题过程。

LeetCode5.0-最长回文子串-中心扩展法-C语言

LeetCode5.1-马拉车算法求解最长回文子串

先简单说一下思路，对于一个回文子串来说，假设长度大于2时，它的首尾一定相等，同时去掉首尾后还是回文子串。这就得到了状态转移方程，从文章（ ）可知，这是动态规划关键步骤一。

如果这个回文子串小于等于2，等于2或者等于1时；我们可以认为长度为1的子串，显然是回文子串；长度为2的子串，只要它的两个字母相同，则为回文子串。这就构成了边界条件。

动态规划关键步骤2，缓冲并复用以往结果。我们需要缓冲的内容是什么，一个二维数组dp[i][j]，该数组表示，以i开头，以j结尾的，长度为j – i + 1的子串是否为回文子串。

dp[i][j] = 0 该子串不是回文子串

dp[i][j] = 1 该子串是回文子串

举例我们的 字符串为 ovvolevel,求出它的最长回文子串。

dp数组举例

dp数组中，对角线都为1，都是回文子串，长度为1，边界条件1。

dp[1][2] = 1 是回文子串，长度为2，指的是vv

dp[5][7] = 1 是回文子串，长度为3，指的是eve

dp[0][3] = 1 是回文子串，长度为4，指的是ovvo

dp[4][8] = 1 是回文子串，长度为5，指的是level

有了以往结果，我们就可以从中找出最长的回文子串作为结果就是dp[4][8] = 1，level。

我们判断dp[4][8] = 1且它的长度level为5比之前的更长，则更新。

动态规划关键步骤三：

按照顺序从小往大算，从小往大时我们的变量表示什么，需要思考一下。我们遍历回文子串的长度从小到大。比如，ovvolevel这个字符串，长度为9，我们分别看它长度为0,1,2,3,4,5,6,7,8时的情况。

遍历结果如下：

回文子串长度为1，strLen = 0，边界条件1，长度为1的子串，显然是回文子串

dp[0][0] = 1 retStr[0] = o

dp[1][1] = 1

dp[2][2] = 1

dp[3][3] = 1

dp[4][4] = 1

dp[5][5] = 1

dp[6][6] = 1

dp[7][7] = 1

dp[8][8] = 1

回文子串长度为2，strLen = 1，边界条件2，长度为2的子串，只要它的两个字母相同，是回文子串

dp[0][1] = 0

dp[1][2] = 1 retStr[0] = v retStr[1] = v

dp[2][3] = 0

dp[3][4] = 0

dp[4][5] = 0

dp[5][6] = 0

dp[6][7] = 0

dp[7][8] = 0

回文子串长度为3

dp[0][2] = 0

dp[1][3] = 0

dp[2][4] = 0

dp[3][5] = 0

dp[4][6] = 0

dp[5][7] = 1 retStr[0] = e retStr[1] = v retStr[2] = e

dp[6][8] = 0

回文子串长度为4

dp[0][3] = 1 retStr[0] = o retStr[1] = v retStr[2] = v retStr[3] = o

dp[1][4] = 0

dp[2][5] = 0

dp[3][6] = 0

dp[4][7] = 0

dp[5][8] = 0

回文子串长度为5

dp[0][4] = 0

dp[1][5] = 0

dp[2][6] = 0

dp[3][7] = 0

dp[4][8] = 1 retStr[0] = l retStr[1] = e retStr[2] = v retStr[3] = e retStr[4] = l

回文子串长度为6

dp[0][5] = 0

dp[1][6] = 0

dp[2][7] = 0

dp[3][8] = 0

回文子串长度为7

dp[0][6] = 0

dp[1][7] = 0

dp[2][8] = 0

回文子串长度为8

dp[0][7] = 0

dp[1][8] = 0

回文子串长度为9

dp[0][8] = 0

动态规划关键三步都搞定，这个问题也就解决了。

完整代码：

leetcode2. 两数相加-c语言-python3

LeetCode4. 寻找两个正序数组的中位数

LeetCode5.0-最长回文子串-中心扩展法-C语言

LeetCode5.1-马拉车算法求解最长回文子串

最长公共子串求解套路

作者 | 码海

出品 | 码海（ID:seaofcode）

头图 | CSDN 下载自东方IC

前言

动态规划是大厂的热门考点，其中最长公共子串与最长公共子序列这两道题出现得尤其频繁，这两道题其实有挺多变种，很适合考察侯选人对动态规划的掌握情况，今天我们就先来看看如何求解最长公共子串，图文并茂，清晰易懂！

最长公共子串

题目如下：

这里需要简单解释下子串与子序列的区别，子串要求这串字符串在原字符串中是连续的，而子序列可以不连续，两者的区别如下：

如果不清楚啥是动态规划的同学，强烈建议先学习下此文，其对动态规划的分析，解题套路中有详细的阐述，好评如潮!对理解动态规划有很大的帮助。

首先看下，如果这题如果用暴力求解的话，应该算出每个字符串的所有子字符串，然后再对所有子字符串进行比较，是个排列组合问题，时间复杂度很大，不可取！所以我们看下怎么用动态规划来解。

解动态规划需要至少明确以下三个概念

• base case

• 状态转移方程

• 自下而上

动态规划一言以蔽之就是利用 「base case 」和「状态转移方程」然后「自下而上」得求得最终问题的解。相对递归的自上而下求解造成的大量子问题的计算，自下而上意味着每个子问题不会被重复计算，很好地达到了「剪枝」的效果。这其中「状态转移方程」的求解无疑是重要的，如果求得了「状态转移」方程，问题其实就解决地差不多了。

回到最长公共子串本身来看，我们来看看它的「状态转移方程」和「base case」是啥。

1、状态转移方程

这题的状态转移方程该怎么定义呢，首先我们求的是两个字符串的公共子串，所以应该意识到这个 dp 方程是个二维数组 dp[i][j]，代表的 x 的前 i 个字符串与 y 的 前 j 个字符串的最长公共子串,那么状态状态方程该怎么得出来呢，一般对于字符串类的动态规划来说，我们可以利用「状态转移表」法来帮助我们得出状态转移方程

观察出规律了吗，对于 dp[i][j] 来说，它的值有两种可能，取决于字符 x[i] 和 y[j] 这两个字符是否相等

如果两个字符相等，则 dp[i][j] = dp[i-1][j-1] + 1（注意图中的箭头）, 怎么理解，1 代表 x 的第 i 个字符与 y 的第 j 个字符相等，根据 dp[i][j] 的定义，那么它自然等于 x 的前 i-1 个字符串与 y 的 前 j-1 个字符串的最长公共子串 + 1，如下图示

如果 x 的第 i 个字符与 y 的第 j 个字符不相等，那么显然 dp[i][j] = 0，因为 dp[i][j] 定义为最长公共子串，所以只要有一个字符不相等，就说明不满足最长公共子串这个定义，自然 dp[i][j] 为 0 了。

根据以上条件可知状态转移方程为

2、base case

显然图中黄色格子所示为 base case

即可用如下公式表示

这也比较好理解，dp[0][i] 或 dp[j][0] 即空字符串与任意字符串的最大公共子串显然为0。

3、求解

有了状态转移方程，有了 base case, 求解不是难事，需要注意的是最长公共子串长度并不是右下角方格子的数字（dp[5][6]）,而是 dp[5][5]，这与一般的动态规划解题套路有些不同，我们可以用一个临时变量来表示最长公共子串。

代码如下：

求解完成，但别忘了分析时间和空间复杂度，看下是否有优化的空间，这两点是很多同学做算法题常见遗漏的地方。

先来看下时间复杂度，两重循环，所以时间复杂度显然为 O(n^2)。空间复杂度呢，二维数组，所以是 O(n^2)，时间复杂度没法优化了，那么空间复杂度呢，其实可以优化为 O(n), 怎么优化，这里就要提一下动态规划的「无后效性」了。

对于各个格子中的数字，它只与其上一行的左上角格子数字有关，与上一行之前的行无关（所以在计算 i = 4 行的格子中，图中 0，1，2 行的格子无需保留），这叫无后效性。

上图中 i=4, j=4 对应的格子中的数字 1 只与其左上角的格子数字 0 有关，所以我们要有一个数组记录其上一行的数字，另外 1 所在行的格子中的数字也要记下来，因为它下一行中格子的数字也是基于本行（1 所在行）的数字推导而来，比如 2 就是基于 1 推导而来的。

由此分析我们要有两个一维数组保留两行的数据，这里的两个数组其实是滚动数组，啥意思呢，我简单解释一下

比如当要计算箭头所指行中格子的数字时，显然，它只与 dp[1] 中格子的数字有关，而与 dp[0] 所指行无关，所以当前行格子的计算结果可以根据 dp[1] 计算出结果放在 dp[0] 中，计算后如下：

现在要计算当前行的格子数，它只与 dp[0] 有关，而与 dp[1] 无关，所以当前行的格子数字可以根据 dp[0] 计算出结果保存在 dp[1] 中。到底是取 dp[0] 还是 dp[1] 呢，这里有一个巧妙的方法：将「当前行&1」的结果与 1 进行比较，比如相等，也就是当前行数为奇数时，则它的结果依赖于 dp[0]，当前行的结果写入 dp[1] 中，如果不相等，也就是当前行为偶数时，则它的结果依赖于 dp[1]，当前行的结果写入 dp[0] 。

优化后的代码如下。

这样的话我们就将空间复杂度优化成了 O(n)。需要说明的事，利用动态规划的无后效性，通常都可以将空间进行压缩，将空间复杂度降低一个层级，所以大家在做完动态规划的算法题后，还是可以再进一步考虑下问题的复杂度是否还可以继续优化。

4、问题变形

以上我们只是简单求了一下最长公共子串的长度，那如何求其对应的子串呢。还是根据状态状态转移来求，但我们要额外加两个变量 max_row, max_column 代表最长公共子串长度对应的格子的坐标。这样根据状态转移方程可以依次反求得其格子对应的字符，如图示:

代码如下：

总结

本文用图文并茂的方式讲述了动态规划的解题套路，相信大家对字符串类型的动态规划解题技巧应该有了进一步的理解，首先最重要的一步当然是明确 dp 的定义，其实字符串类的动态规划问题一般可以用状态转移表法来观察状态转移方程，得出了状态转移方程，思路也就厘清得八九不离十了，另外当解决完之后，最好思考一下时间/空间复杂度是否有优化的空间，一般可以根据动态规划的无后效性来进一步优化复杂度，通过这样不断地优化自然可以得出问题的最优解。

点分享

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com