LeetCode-Longest Palindromic Subsequence
原创LeetCode-Longest Palindromic Subsequence
原创
版权声明：本文为博主原创文章，转载请注明原文出处！
写作时间：2019-02-10 11:44:52
Longest Palindromic Subsequence
题目描述
这是LeetCode的第516道题目：516. Longest Palindromic Subsequence。
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"Output:
4One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:
"cbbd"Output:
2One possible longest palindromic subsequence is "bb".
题目要求我们计算出给定字符串中的最长回文序列（这里的序列不是一定要在给定字符串中连续排列的，就是挑出的单个字符按其在给定字符串中的顺序排列以后是回文即可）
思路分析
其实，思路跟第647道题目Palindromic Substrings是类似的，可以采用动态规划进行。但是因为回文序列不是给定字符串的连续子串，貌似不能使用中心扩散法求解。
使用动态规划，我们设dp[i][j]表示从第i个字符到到j个字符回文序列的长度，则有：
- 当
s[i] == s[j]时，dp[i][j] = dp[i+1][j-1] + 2 - 当
s[i] != s[j]时，dp[i][j] = max(dp[i+1][j], dp[i][j-1])
C++实现
class Solution {
public:
int longestPalindromeSubseq(string s) {
const int length = s.length();
vector<vector<int>> dp(length, vector<int>(length));
for (auto i = length - 1; i >= 0; --i) {
dp[i][i] = 1;
for (auto j = i + 1; j < length; ++j) {
dp[i][j] = s[i] == s[j] ?
dp[i + 1][j - 1] + 2 :
max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][length - 1];
}
};Scala实现
Scala版本是对C++版本的翻译
object Solution {
def longestPalindromeSubseq(s: String): Int = {
val length = s.length
val dp = Array.ofDim[Int](length, length)
for (i <- length - 1 to 0 by -1) {
dp(i)(i) = 1
for (j <- i + 1 until length) {
dp(i)(j) = if (s(i) == s(j)) dp(i + 1)(j - 1) + 2
else math.max(dp(i + 1)(j), dp(i)(j - 1))
}
}
return dp(0)(length - 1)
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。