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]: 表示从i到j的子串中包含的最长回文长度。
采用从后向前遍历，如果第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。

解题代码

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];
  }