最长回文子串:结合图形推导动态规划

题目介绍

本题可以在力扣找到,题号为5。
给你一个字符串 s,找到 s 中最长的 回文子串。

示例 1:

输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:

输入:s = “cbbd”
输出:“bb”

提示:

1 <= s.length <= 1000
s 仅由数字和英文字母组成

暴力解法

先从暴力解法入手,对于长度为n的字符串,总共有 (n+1) * n / 2 种组合,我们可以找出每种组合,然后判断其是否是回文串,最后与当前的最大值进行比较,若新串更大,就更新答案。

我们先写一个判断回文串的函数,用双指针判断即可:

    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

然后我们用双重循环,遍历到每一种可能,在进行进一步判断:

class Solution {
    public String longestPalindrome(String s) {
        String resp = "";
        int ans = 0;
        int[][] dp = new int[s.length()][s.length()];
        int n = s.length();
        for (int i = 0;i < n;i++) {
            for (int j = i;j < n;j++) {
            	//获取子串
                String subString = s.substring(i,j+1);
                //判断是否要更新最长子串
                if (subString.length() > resp.length() && isPalindrome(subString)) {
                    resp = subString;
                }
            }
        }
        //返回答案
        return resp;
    }

    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

动态规划

接下来我们可以考虑动态规划的解法,所谓动态规划,就是用之前的状态递推后面的状态。首先我们需要确定一个状态转移条件,对于一个 字符串 来说,如果有 一个子串str 为回文串,且 str的前一个字符和后一个字符也相同(比如说 “aba” 和 “aabaa”)那么就说明 [str-1,str+1] 也为回文串。我们可以定一个二维数组,将其定义为 从 i 到 j 的子串是否是回文串:

//初始化一个状态数组--布尔类型
int[][] dp = new int[n][n];
for (int i = 0;i < n;i++) {
	//对于单个字符的情况,必定为回文串
	dp[i][i] = true;
}

根据我们之前的结论,可以推出状态转移方程,即

if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == true) {
	dp[i][j] = true;
} else {
	dp[i][j] = false;
}

可以看到,dp[i][j]的状态是基于 dp[i+1][j-1]的,即若要得到 dp[i][j],则要先得到dp[i+1][j-1]的状态,光这么描述其实还是很抽象,我们借助矩阵图来理解:
在这里插入图片描述
我们把横轴作为j,纵轴作为i,首先我们可以填充 dp[i][i],即只有一个字符的情况,都可以填充为true:
在这里插入图片描述
其次,对于j > i 的情况其实都可以不用考虑,因为起始位置是要始终小于结束位置的:
在这里插入图片描述
接着,我们推到一般情况的依赖关系,我们先任选一点,比如 dp[0][2],根据状态转移方程,我们需要参考的就是 dp[1][1] 的状态值了:
在这里插入图片描述
即,对于每一个状态,在二位图像上总是需要依赖其左下角的具体状态,所以理论上来说,只要从对线向右上填充,我们就可以得到整个dp数组的状态了:
在这里插入图片描述
对于上面的示例来说,只要我们填充了 i = j 以及 i + 1 = j 这两条对角线,我们就可以成功推导出整个dp数组的状态,接下来我们开始编程实现:

    public static String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        //填充对角线
        for (int i = 0;i < n;i++) {
            dp[i][i] = true;
        }
        //填充 j = i + 1
        for (int i = 0;i < n-1;i++) {
            int j = i + 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = true;
            }
        }
        //填充其余情况,按对角线顺序填充
        for (int offset = 0;offset < n-2;offset++) {
            for (int i = 0;i < n-2-offset;i++) {
                int j = i + 2 + offset;
                if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {
                    dp[i][j] = true;
                }
            }
        }
        //遍历dp数组,求出最长值
        int longestLength = 0;
        String resp = "";
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                if (dp[i][j] && j - i + 1 > longestLength) {
                    longestLength = j - i + 1;
                    resp = s.substring(i,j+1);
                }
            }
        }
        return resp;
    }

具体实现就如上,需要注意的是,由于 dp[i][j] 依赖于 dp[i+1][j-1],即依赖于左下角的状态,所以我们填充一般状态的时候也需要按照这个顺序填充,即需要按照对角线层层填充才能得到正确答案。

我们可以与暴力做法的耗时作比较,暴力解法耗时大概在 1000ms左右,而上面这种基于动态规划的解法耗时只有 200ms左右:
在这里插入图片描述
大幅优化了耗时,不过上述解法中还有可以改进的地方,比如我们可以在填充dp数组的时候就开始寻找答案,而不是分两步走:

    public static String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        //填充对角线
        for (int i = 0;i < n;i++) {
            dp[i][i] = true;
        }
        int longestLength = 1;
        String resp = s.charAt(0) + "";
        //填充 j = i + 1
        for (int i = 0;i < n-1;i++) {
            int j = i + 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = true;
                if (j - i + 1 > longestLength) {
                    longestLength = j - i + 1;
                    resp = s.substring(i,j+1);
                }
            }
        }
        //填充其余情况,按对角线顺序填充
        for (int offset = 0;offset < n-2;offset++) {
            for (int i = 0;i < n-2-offset;i++) {
                int j = i + 2 + offset;
                if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {
                    dp[i][j] = true;
                    //将判断步骤放入填充步骤中
                    if (j - i + 1 > longestLength) {
                        longestLength = j - i + 1;
                        resp = s.substring(i,j+1);
                    }
                }
            }
        }
        return resp;
    }

这样我们就可以省去一次遍历的开销,最终优化效果到 139ms 左右:
在这里插入图片描述

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部