LeetCode 516. Longest Palindromic Subsequence

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/02/27/LeetCode-516-Longest-Palindromic-Subsequence/

访问原文「LeetCode 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:
4

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

“cbbd”
Output:
2

One possible longest palindromic subsequence is “bb”.

题意解析

查找一个字符串中包含的最长回文长度。

解法分析

这道题的主要解法就是动态规划。
f[i][j]: 表示从ij的子串中包含的最长回文长度。
采用从后向前遍历,如果第i个字符与第j个字符相同,f[i][j] = f[i+1][j-1] + 2,否则f[i][j] = Math.max(f[i+1][j], f[i][j-1])。初始化时f[i][i] = 1

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int longestPalindromeSubseq(String s) {
if(s == null || s.length <= 0){
return 0;
}
int[][] f = new int[s.length()][s.length()];
for (int i = s.length() - 1; i >= 0; i--) {
f[i][i] = 1;
for (int j = i+1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i+1][j-1] + 2;
} else {
f[i][j] = Math.max(f[i+1][j], f[i][j-1]);
}
}
}
return f[0][s.length()-1];
}