美文网首页
LeetCode 第516题:最长回文子序列

LeetCode 第516题:最长回文子序列

作者: 放开那个BUG | 来源:发表于2020-11-22 12:30 被阅读0次

1、前言

题目描述

2、思路

定义一个二维数组 dp[i][j],表示:在子串 s[i ... j] 中,最长回文字串的长度为 dp[i][j]。

关于 dp[i][j] 的递推状态:在 dp[i + 1][j - 1] 时,s[i] == s[j],那么加上这两个字符即可(加2);如果 s[i] != s[j],那么就分别加上一个字符,看哪个最大,即 max{ dp[i][j - 1], dp[i + 1][j] }。

关于 base case:因为 i 不可能大于 j,所以 i 大于 j 的地方都是 0;如果 i == j,那么说明字符只有一个,那么此时都是 1;我们最终是求 dp[0][n - 1](n 是字符串的长度)。

然后就是遍历方式,这道题可以画出一个二维数组,发现只能反着或者斜着遍历才能从已知递推到未知。

但是这道题一个终极最简单的方法:利用两个字符串的最长公共子序列来做。我们可以将原字符串 s 反转成 k,然后求 s 和 k 的最长公共子序列,这个子序列就是最长回文子序列。

3、代码

public class LongestPalindromeSubseq {

    public int longestPalindromeSubseq(String s) {
        int m = s.length();
        int[][] dp = new int[m][m];

        for(int i = 0; i < m; i++){
            dp[i][i] = 1;
        }


        // 为什么要反向遍历,已经二维表是由已知推未知,
        // 只有这种方式才能满足根据旁边三个角的值推到最终值
        for(int i = m - 1; i >= 0; i--){
            for(int j = i + 1; j < m; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }

        return dp[0][m - 1];
    }

    /**
     * 使用两个数组最长子序列的思路,先将 s 反转成 k,然后求 s 和 k 的子序列
     * @param s
     * @return
     */
    public int longestPalindromeSubseq2(String s) {
        int m = s.length();
        int[][] dp = new int[m + 1][m + 1];
        String k = new StringBuilder(s).reverse().toString();

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= m; j++){
                if(s.charAt(i - 1) == k.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][m];
    }

    public static void main(String[] args) {
        String s = "bbbab";
        System.out.println(new LongestPalindromeSubseq().longestPalindromeSubseq2(s));
    }
}

相关文章

网友评论

      本文标题:LeetCode 第516题:最长回文子序列

      本文链接:https://www.haomeiwen.com/subject/kqyeiktx.html