头脑风暴:最长回文子序列
题目
给定一个字符串 s ,找到其中最长的回文子序列,并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1:输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。
示例 2:输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。
提示:
1 <= s.length <= 1000
s 只包含小写英文字母
解题思路
根据题意,本题可使用动态规划的方式来求解。
第一步,确定 dp 数组以及下标的含义:
dp[i][j]:字符串 s 在[i, j]范围内最长的回文子序列的长度为 dp[i][j]。
第二步,确定递推公式:
在判断回文子串的题目中,关键逻辑就是看 s[i]与 s[j]是否相同。
如果 s[i]与 s[j]相同,那么 dp[i][j] = dp[i + 1][j - 1] + 2;
如果 s[i]与 s[j]不相同,那么 dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
第三步,dp 数组初始化:当 i 与 j 相同,那么 dp[i][j]一定是等于 1,其他情况 dp[i][j]初始为 0。
代码实现
复制代码
最后
时间复杂度:O(n^2),其中 n 是字符串 s 的长度。
空间复杂度::O(n^2),其中 n 是字符串 s 的长度。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/91e75a3ee1f0efcc65f11a00c】。文章转载请联系作者。
评论