算法题:最长回文子串

Scroll Down

题目描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"

前言:在两三个月前,这道题练过,现在记忆上有点模糊,今天在把这道题刷一遍,巩固一下。

LeetCode上的记录。
image.png

解题思路:
1.首先,我们要解题,那么我们就要知道回文串的概念,回文串,我这里就简单的讲一下,就是类似于,ABA,AABB这种,具体的,大家可以自行百度,这个很好理解。再者呢,就是理解子串的概念,子串和子序列容易搞混,希望大家也可以自行百度,要是题都不懂,那么就别说解题了。

2.子串,想到子串,那么我们以前做过的算法题里面有,求出一个字符串的所有子串,然后再一个一个去对比,但是如果用的是这种解法的话,时间复杂度达到了O(n3)这是完全不能忍受的,所以我们要想想怎么优化。

3.优化,我们想一下,首先我们题目要求是要所有子串的,但是求所有子串据我了解的最低的时间复杂度就是O(n2),所以我们把优化方向,放到求解回文串上,如果我们能将求出回文串只要O(1)的复杂度,那么整个题目就可以优化一个量级。

4.实现,我们可以用到动态规划来解,怎么解呢,我们判断一个字符串是不是回文串,那么我们首先要判断,首字母和尾字母是否相等,然后依次向前推。哪么如果我们已经记录了去掉收尾字母的子串是否是回文串,哪不就解决了吗。

代码实现:

     public  String longestPalindrome(String s) {
          if(s.length()<2)return s;
          int len = s.length();
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[len][len];
//对于字符本身,它是回文串。
//初始化。
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int begin = 0;
        int res = 1;
//求所有子串
//这里面求所有子串的方法是有讲究的,间隔是逐渐增大的,为了DP好计算。
        for (int i = 0; i < len; i++) {
            for (int start = 0, end = i + 1; end < len; end++, start++) {
                if (chars[start] == chars[end]) {
                    if (end - start + 1 <= 3) {
 //子串长度小于3,直接设为True
                        dp[start][end] = true;
                    } else {
                        dp[start][end] = dp[start + 1][end - 1];
                    }
                } else {
                    dp[start][end] = false;
                }
                if (dp[start][end]) {
                    int curLen = end - start + 1;
//记录最长的子串
                    if (curLen > res) {
                        res = curLen;
                        begin = start;
                    }
                }

            }
        }
        return s.substring(begin, res + begin);
    }

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/