用什么服务器做盗版小说网站吗,东莞企业网,本地常州网站建设,小程序注册完成后如何制作本期主讲的是使用动态规划去解决两道回文问题#xff0c;分别是
647. 回文子串 - 力扣#xff08;LeetCode#xff09;
516. 最长回文子序列 - 力扣#xff08;LeetCode#xff09;
而不是leetcode5.最长回文子串#xff0c;虽然这道题也是回文问题#xff0c;也可以…本期主讲的是使用动态规划去解决两道回文问题分别是
647. 回文子串 - 力扣LeetCode
516. 最长回文子序列 - 力扣LeetCode
而不是leetcode5.最长回文子串虽然这道题也是回文问题也可以使用dp来解决但是这道题本人认为与647回文子串思路相同但这里也给出大致的解题思路。
这道题求的是连续子数组问题而且是最长的回文的子数组虽然它只有一个字符串但是我们也使用二维dp数组一维代表起始子数组另一维是标识该子数组的终点然后从后往前遍历字符串两层循环分别指子串起始和末尾然后判断当前两个下标对应字符是否相等然后再看中间的子数组是否回文若是则更新答案。
这道题的思路其实就是我们要讲的回文子串的思路只不过处理数据有些不同而已求最长子数组就是记录当前多长和之前的比较。而这道记录的是有多少回文子串实际思路是相同的 第一道题
先看代码
class Solution {
public:int countSubstrings(string s) {int ns.size();vectorvectorbooldp(n,vectorbool(n,false));int res0;for(int in-1;i0;--i){for(int ji;jn;j){if(s[i]s[j]){if(j-i1){dp[i][j]true;res;}else if(dp[i1][j-1]){dp[i][j]true;res;}}}}return res;}
}; 我们以一个布尔类型二维数组做判断循环就是刚才说的从后往前为什么从后往前这是因为递推式的缘故我们要判断当前字符相等的情况下看一看该子串里面的内容是否回文怎么看它是比较i1和j-1所以一定要保证这一段已经被判断回文过了所以我们才会选择从后往前遍历的方法而内层循环你看着可能有些奇怪但事实上它是正确的。因为如果两个下标对应相等还存在两种情况一种是两下标指向同一字符此时肯定回文另一种是指向不同字符但是这两个下标只差1也就是说【a】和【aa】这两种情况的对应。我们都考虑了进来当两下标相差大的时候里面就会存有子数组我们才会进行判断而此时判断的话已经是之前遍历过的位置了已经知道了它回不回文。
可能有读者会问是否可以从字符串中间去进行向两边扩散的访问以得到是否回文的情况这一招很好用对于判断整个字符串是否回文以及判断整个字符串的最长回文子数组的长度但是并不适用于本题因为本题求解的是根据每一个下标的情况给出可能存在的所有回文的子数组的个数
而上面的那招中心探测并不完全如果使用中心探测至少要对每个子串都进行回文判断所以无论如何你都逃脱不了要判断每个子串的命运而不是只在字符串的中心位置判断回文而只On就能解决问题你最少需要ON^2才可以解决问题。至少我知道的方法里没有ON
当然如果你是算法老鸟你可以对二维数组进行一维的压缩以解决减少时间复杂度的开销但是通常我只会在简单的题解里才会想这种优化稍稍复杂一点的题解很容易出现各种问题所以我一般倾向于解题而不是给自己找麻烦。 第二道题 最长回文子序列是不是看起来和那道最长回文子串差不多这道题只不过是求不连续的子序列最长的长度。
但我们这里的思路并不沿用上面的思路。尽量不要使用回文子串那道题目的做法会使得代码难写且含义不清晰因为那道做法dp含义是针对于连续子数组的我们很难只用true或false来判断中间字符串的回文长度到底为多少而且在本题中这样的bool数组并没有太多价值因为如果要存子序列的最长数多半情况是用到其他变量辅助存储的而bool数组起到的作用只是判断这段子数组是否回文与这道题实际的问题有点相违背。
这道题我们采用如下的思路
class Solution {
public:int longestPalindromeSubseq(string s) {int ns.size();vectorvectorintdp(n,vectorint(n,0));for(int i0;in;i)dp[i][i]1;for(int in-1;i0;--i){for(int ji1;js.size();j){if(s[i]s[j])dp[i][j]dp[i1][j-1]2;else dp[i][j]max(dp[i][j-1],dp[i1][j]);}}return dp[0][n-1];}
}; dp数组的含义代表当前ij范围内最长的回文子序列多长子序列可以不连续 当此时ij对应下标字符相等则用两下标中间的子串范围的最大回文子序列长度2也就是把s【i】和s【j】都加入进来 如果此时不相等则判断如果只加进一个能否取得最长回文子序列也就是说dp【i】【j-1】和dp【i1】【j】它们两个比较然后取最大值。 为什么这样呢因为s【i】和s【j】中间的子数组应该是以s【i1】和s【j-1】为下标的所以左边加进来s【i】就是dp【i】【j-1】右边加进来j就是dp【i1】【j】 别忘了根据递推式的含义最后返回的应该是dp【0】【s.size-1】 代表从0开始到结束最长的回文子序列
是不是有疑问了为什么这道题的内部循环变得更奇怪了要使用ji1的初始化这样不会越界吗
接下来我们来解释一下这样做的原因。
里层循环i1并不是无用的不能设置为ji 有两个原因一个是浅显易见的是因为两个下标指向同一字符的情况我们已经初始完毕了另一原因是如果从ji进来那第一次填数会导致数组非法下标访问而第二次进来虽然推导时候也有些奇怪因为i和j拉开距离过小的缘故i会走到j的位置也就是i上一次遍历的位置j会走到i本次起始遍历位置虽然奇怪但是也是遍历过的所以答案也是对的。
没错前面的循环是为了初始化因为至少它的最长回文子序列一定是1我们要把它初始化一下这也方便接下来dp数组的正确填数。而由于递推式的缘故我们也不能使内层循环写成ji开始要不然一开始就会越界这道题不像上一道题上一道题是极可能存在相邻两个相等的情况而且那道题的dp数组含义也与本题不同。那道题ji的初始化由于前面的if判断ji的时候会有一个缓冲不会过早进到中间子数组的判断这道题递推式不行它不具备那样的缓冲。
那我们可以加一个那样的判断吗判断两字符相等且jI然后填数做缓冲不就可以了吗
好问题可以
但是求子序列的含义是我们可以允许不相邻的子序列也构成答案也就是说子序列答案是包含了两个字符相邻回文也就是子序列包含子数组的所有情况没必要写一个特式专门用来判断这一步骤这显得有点繁琐了子序列的代码应该更适用于大多数的情况。
但如果加一步那样的判别可以使一开始的判断回文看起来正常一些j也不用从i1开始判断了也是一种好的题解思路。
那这道题可以从字符串中间进行下标的开始匹配吗我认为有点问题类中心探测法无论是一次匹配还是每个字符的分别匹配本质上都是用来解决连续的子数组的问题用在子序列可能有点麻烦我没有试过感兴趣的读者可以自己试一下。我认为应该有点难度。 都看到这里了如果对您有用的话别忘了一键三连哦如果是互粉回访我也会做的
大家有什么想看的题解或者想看的算法专栏、数据结构专栏可以去看看往期的文章有想看的新题目或者专栏也可以评论区写出来讨论一番本账号将持续更新。 期待您的关注
