大厂面试真题详解:最长的回文序列

给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.

在线评测地址:领扣题库官网

样例1

输入: "bbbab"
输出: 4
解释:
一个可能的最长回文序列为 "bbbb"

样例2

输入: "bbbbb"
输出: 5

算法:DP

设dpi表示在s[i...j]中最长回文序列的长度。
对于初始化区间长度

  • 长度为0时,dpi = 1
  • 对于 dpi,假设s[i] != s[j]

    • 那么在sub(i,j)的最大回文串中,s[i]与s[j]不会同时出现,那么sub(i,j)的最大回文串要么出现在sub(i+1,j),要么出现在sub(i,j-1),因此我们的状态转移方程就得到了dpi = max(dpi+1, dpi)
  • 假设s[i]==s[j]

    • 那么直接认为这俩个匹配,会同时出现在结果中,然后加上sub(i+1,j-1)的最大回文串,即dpi = dpi+1 + 2
  • 最后的结果就在dp0

复杂度分析

  • 时间复杂度O(len(s)*len(s))

    • 嵌套循环,顺着i减小的方向,以j增大的方向遍历
  • 空间复杂度O(len(s)*len(s))

    • 二维dp的大小
public class Solution {
    /**
     * @param s: the maximum length of s is 1000
     * @return: the longest palindromic subsequence's length
     */
    public int longestPalindromeSubseq(String s) {
        int size = s.length();
        char[] ss = s.toCharArray();
        if (size <= 1){
            return size;
        }
        int[][] dp = new int[size][size];
        //初始化        
        for (int i = 0; i < size; ++i) {
            dp[i][i] = 1;
        }
        for (int i = size - 1; i >= 0; --i) {
            for (int j = i + 1; j < size; ++j) {
                if (ss[i] == ss[j]) {//s[i]==s[j]时的转移方程
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } 
                else {//s[i]!=s[j]时的转移方程
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        //最后结果在dp[0][size - 1]中
        return dp[0][size - 1];
    }
}

更多题解参考:九章官网solution

上一篇:采集频率的动态调整策略


下一篇:大厂面试真题详解:字符串解码