# LeetCode刷题笔记5最长回文子串

这是我参与更文挑战的第2天，活动详情查看： 更文挑战

笔记重点：使用动态规划来处理最长回文子串的问题。

题目地址：leetcode-cn.com/problems/lo…

题目描述：

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

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

输入：s = “cbbd”
输出：”bb”
示例 3：

输入：s = “a”
输出：”a”
示例 4：

输入：s = “ac”
输出：”a”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成。

自我题解：暴力循环

要处理这个问题，

回文串（palindromic string）是指这个字符串无论从左读还是从右读，所读的顺序是一样的；简而言之，回文串是左右对称的。

既然是最大回文子串，很正常的我们想到从子串由大到小开始遍历，当遇到满足回文的要求时，就直接返回当前子串。

/**
     * 判断是否是回文
     * */
    private boolean isPalindrome(String s){
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 暴力求解
     * */
    private String solution1(String s){
        if(s == null || s.length() == 0){
            return s;
        }
        for (int l = s.length(); l>1;l--){
            int start = 0; int end = l;
            while (end<=s.length()){
                String s1 = s.substring(start,end);
                if(isPalindrome(s1)){
                    return s1;
                }
                start++;
                end++;
            }
        }
        return s.charAt(0)+"";
    }
复制代码

官方题解：动态规划

什么是动态规划？参考

www.cnblogs.com/cthon/p/925…

我么知道动态规划有三个比较重要的东西

1. 最优子结构
2. 状态转移方程
3. 边界条件

建立模型

对于一个字符串s = “ababa”,要判断它是不是一个回文字符串我们需要判断第一个和最后一个字符是否相等，在相等的情况下需要判断bab是否是回文字符串。

我们假设起始位置为 i j

状态转移方程如下

F [i] [j] = s[i] == s[j] && f[i-1] [j-1]

边界条件是：

i==j 时 只有一个字符 是回文

i+1 = j 时 如果s [i] == s[j] 它是回文

i+2 = j 时 如果s [i] == s[j] 它是回文

最优子结构

从状态转移方程我们可以知道 当前第一个和最后一个字符是否相等和除去第一个和最后一个字符剩余的字符串是否为回文。是最优子结构。

动态规划求解

根据动态规划的学习了解，我们肯定不能用递归来实现，因为递归时间复杂度是指数阶的。我们用一个二维数组将每一个中间数据的结果保存下来。为了节省空间，我们不全量保存。那么需要保存那些内容呢？我们借助图标观察下他们之间的关系

以dcababacd为例

因为i一定小于等于j 右上部分不用填写。

填写边界条件：

因为当子字符串的长度为1的时候一定是回文字符串，因此对角线都为true

当子串长度为2或3的时候不依赖其它位置。

表格填表说明：

代码：

public String solution3(String s){
        if(s == null || s.length() == 1){
            return s;
        }
        int maxLen = 1;
        HashMap<PositionKey,Boolean> positionInfo1 = new HashMap<>();
        HashMap<PositionKey,Boolean> positionInfo2 = new HashMap<>();
        HashMap<PositionKey,Boolean> temp = null;
        int begin = 0;
        int len = s.length();
        for (int L = 2; L <= len; L++) {
            for (int i=0;i<=len-L;i++){
                int j = L + i -1;
                boolean value = s.charAt(i) == s.charAt(j);
                if(L == 2){
                    positionInfo1.put(new PositionKey(i,j), value);
                }else if(L == 3){
                    positionInfo2.put(new PositionKey(i,j), value);
                }else {
                    if(temp == null){
                        temp = new HashMap<>();
                    }
                    temp.put(new PositionKey(i,j), value && positionInfo1.get(new PositionKey(i+1,j-1)));
                }
                if(value && L > maxLen){//是回文
                    if(L == 2 || L == 3){
                        begin = i;
                        maxLen = L;
                    }else if(positionInfo1.get(new PositionKey(i+1,j-1))){
                        begin = i;
                        maxLen = L;
                    }
                }

            }
            if(temp != null){
                positionInfo1 = positionInfo2;
                positionInfo2 = temp;
                temp = null;
            }

        }
        return s.substring(begin,begin+maxLen);
    }
复制代码

从这个题目中我们需要了解什么是动态规划，动态规划的3个比较重要的东西。

官方题解：中心扩展算法

中心扩展算法叶的特点是，利用回文的对称性，由中间向两边进行扩展，如果首位值不相同停止扩展。否则一直扩展到不能增加。但是需要注意的是，回文总个数有可能是奇数也有可能是偶数，因次两种场景都要覆盖到。