美文网首页
5. 最长回文子串 动态规划 解法2

5. 最长回文子串 动态规划 解法2

作者: 滨岩 | 来源:发表于2020-12-14 23:57 被阅读0次
    image.png

    暴力解法,判断每一种可能,我们想,是不是判断的太多了,比如已知aba是回文串,那么判断babab串时需要从头开始一步一步判断吗?答案是不需要的,我们可以利用动态规划来记录状态,并且使用状态转移方程减少不必要的判断

    首先定义状态 一维数组 dp[i,j],表示从第i个到第j个字符来表示是否是回文串,然后定义状态转移方程
    dp[i,j]=dp[i+1][j-1]&&str[i]==str[j]

    表示判断dp[i,j] 是否回文串,首先得满足 dp[i+1][j-1] 是回文串 且 str[i]==str[j]

    image.png

    我们模拟一下

    首先
    1、dp[0][0]: b==b,dp[0][0]=true;
    2、dp[0][1]: b!=a,dp[0][1]=false;
    3、dp[0][2]:(b==b&&dp[1][1]);
    ...

    这时候发现 dp[1][1] 还没赋值,还没有这个状态?
    而且我们发现,从头遍历的字符串都长,要想重复利用,也是重复利用从后面开头的字符串,所以状态的递推需要从后面开始

    我们倒置再模拟一下
    首先

    dp[5][5]: d==d dp[5][5]=true;
    dp[4][4]: b==b dp[4][4]=true;
    dp[4][5]=(b==d)=false
    dp[3][3]=true,dp[3,4]=(a==b)=false;
    dp[3][5]=((a==d)&&dp[4][4])=false
    ...
    可见,我们成功使用了之前已经判断的字符串,状态重复使用成功

    不过我们使用了双层循环,时间复杂度仍然是log(n^2)

      /**
         * dp[i][j]  表示 从i 到j  的字符串是否是回文
         * 状态转移公式   dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]
         *
         * @param s
         * @return
         */
        public String longestPalindrome(String s) {
    
            boolean[][] dp = new boolean[s.length()][s.length()];
    
            int start = 0;
            int max = 1;
            for (int i = s.length() - 1; i >= 0; i--) {
                for (int j = i; j < s.length(); j++) {
    
    
                    boolean sret = (s.charAt(i) == s.charAt(j));
    
                    dp[i][j] = sret;
    
                    if (i + 1 <= j - 1) {
                        dp[i][j] = sret && dp[i + 1][j - 1];
                    }
    
    
                    if (dp[i][j] && (j - i + 1 > max)) {
                        start = i;
                        max = j - i + 1;
                    }
    
                }
            }
    
            return s.substring(start, start + max);
        }
    

    相关文章

      网友评论

          本文标题:5. 最长回文子串 动态规划 解法2

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