题解 | #最长回文子序列#
最长回文子序列
http://www.nowcoder.com/practice/c7fc893654b44324b6763dea095ceaaf
最长回文子序列
问题描述：给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。字符串长度<=5000
示例
输入："abccsb"
返回值：4
说明：子序列bccb回文序列为bccb，因此最长的回文子序列长度为4
方法一
思路分析
最长回文子序列表示子序列在给定的序列中位置可以是不连续的。使用递归的办法，采用自上而下的办法，要求的string[0,n-1]中开始元素到末尾元素中间的最长回文子序列，有如下递归方程：
- 设置$lps(string ,i,j)$表示字符串string中第i个位置到第j个位置中的最长回文子序列
- 设置$lps(string ,i,j)=1，i=j$，同时这也是递归结束的条件
- 如果首尾元素相同，那么$lps(string ,i,j)=lps(string ,i+1,j-1)+2$
- 如果首尾元素不同，那么$lps(string ,i,j)=max\{ lps(string ,i+1,j)，lps(string ,i,j-1)\}$
图解
输入："abccsb"，递归过程如下图：
| 0 | 1 | 2 | 3 | 4 | 5 |
| a | b | c | c | s | b |
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string 一个字符串由小写字母构成，长度小于5000
* @return int
*/
int longestPalindromeSubSeq(string s) {
// write code here
int n=s.size();
return lps(s,0,n-1);
}
int lps(string str, int i, int j)
{
if (i == j)
return 1; //只有一个元素，回文长度为1
if (i > j) return 0; //因为只计算序列str[i....j]
//如果首尾相同
if (str[i] == str[j])
return lps(str, i + 1, j - 1) + 2;
//如果首尾不同
return max(lps(str, i, j - 1), lps(str, i + 1, j));
}
}; 复杂度分析
- 时间复杂度：有许多相同的子问题会被重复计算，这是递归的一个问题，递归的时间复杂度为递归的次数*每次递归的操作次数，递归次数为$n^2$，因此时间复杂度为$O(n^2)$，该方***超时
- 空间复杂度：递归的空间复杂度为递归的深度*每次递归创建的变量，递归深度为$n$，每次递归的空间复杂度为$O(1)$，因此空间复杂度为$O(n)$
方法二
思路分析
在使用递归的方法时由于采用自上而下的办法，因此有些子问题被重复计算，为了避免这种问题，我们还可以采用自下而上的办法，即采用动态规划的办法，即借助一个二维数组dp[i][j]存储已经计算过的子问题，即第i个位置到第j个位置最长回文子序列的长度。使用动态规划的转移方程为：
- 所有连续的长度为i+1的子串，$str[j..j+i]$
- 如果$dp[i][i]=1 i=j$
- 如果首尾元素相同那么$dp[j][j+i]=dp[j+1][j+i-1]+2$
- 如果首尾元素不同那么$dp[j][j+i]=max\{dp[j+1][j+i],dp[j][j+i-1]\}$
- 最后输出$dp[0][n-1]$即为给定字符串的最长回文子串
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string 一个字符串由小写字母构成，长度小于5000
* @return int
*/
int longestPalindromeSubSeq(string s) {
// write code here
int n=s.size();
return lpsDp(s,n);
}
int lpsDp(string str, int n)
{
int tmp;
vector<vector<int>> dp(n,vector<int>(n,0));
for (int i = 0; i < n; ++i)
dp[i][i] = 1;
for (int i = 1; i < n; ++i)
{
tmp = 0;
//考虑所有连续的长度为i+1的子串，str[j....j+i]
for (int j = 0; j + i < n; j++)
{
if (str[j] == str[j + i])//如果首尾相同
tmp = dp[j + 1][j + i - 1] + 2;
else //如果首尾不同
tmp = max(dp[j + 1][j + i], dp[j][j + i - 1]);
dp[j][j + i] = tmp;
}
}
return dp[0][n - 1]; //返回字符串str[0...n-1]的最长回文子序列长度
}
}; 复杂度分析
- 时间复杂度：内外层循环次数为$1+2+3+...+n=n*(n+1)/2$，因此时间复杂度为$O(n^2)$
- 空间复杂度：借助于一个二维数组存储当前位置的最长回文子序列长度，空间复杂度为$O(n^2)$
方法三
思路分析
为进一步减小空间的使用，在方法二中可以发现求解$dp[i][j]$数组只与相邻状态有关，因此可以设置一个一维的数组。
python核心代码
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string 一个字符串由小写字母构成，长度小于5000 # @return int # class Solution: def longestPalindromeSubSeq(self , s ): # write code here dp = [1] * len(s) for i in range(len(s)-1, -1, -1): pre = 0 # dp[i+1][j-1] for j in range(i+1, len(s)): temp = dp[j] if s[i] == s[j]: dp[j] = pre + 2 else: dp[j] = max(dp[j], dp[j-1]) pre = temp return dp[-1]
复杂度分析
- 时间复杂度：内外层循环次数为$1+2+3...+n=n*(n+1)/2$，因此时间复杂度为$O(n^2)$
- 空间复杂度：借助于一个一维数组，空间复杂度为$O(1)$
投递美团等公司10个岗位 >
华为工作强度 827人发布