题目形容

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

例子

<code class="txt">示例 1：
输出：s = "babad"
输入："bab"
解释："aba" 同样是合乎题意的答案。

示例 2：
输出：s = "cbbd"
输入："bb"

示例 3：
输出：s = "a"
输入："a"

示例 4：
输出：s = "ac"
输入："a"

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…，著作权归领扣网络所有。

思路以及解答

暴力破解

暴力破解，即是针对外面每一个子串，都去判断是否为回文串。

判断每一个字符是不是回文串，比方用 cbac 判断，左右两个指针，对称判断，相等则往两头挪动，持续判断，不相等则间接返回 false 。

<code class="java">    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        String result = s.substring(0, 1);
        for (int i=0; i < s.length() - 1; i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (judge(s, i, j) && j - i + 1 > result.length()) {
                    result = s.substring(i, j+1);
                }
            }
        }
        return result;
    }
    
    // 判断每个子串是不是回文
    public static boolean judge(String source, int start, int end) {
        // 对称轴比照
        while (start <= end) {
            if (source.charAt(start) != source.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

暴力破解简单度过高，会超时，不举荐应用。

核心拓展法

回文串总是中心对称的，后面使用暴力法的时候，都是截取出子串之后再判断，只有判断到全副对称，能力证实回文，这样其实走了很多弯路，只有最初一个不对称，半途而废。

反过来想，咱们不如在每一个点，都尝试往两边拓展，这样只有不匹配，就能够及时止顺。

值得注意的是，核心拓展法的核心怎么找？3个字符有多少个核心呢？

一共有五个核心，有些核心可能是两个字符的间隙，有些核心可能是字符。那么设计的时候，咱们用 left 和 right 示意两个指针：

• left = right：对称中心为字符
• left + 1 = right: 对称中心为两个字符的间隙

具体实现如下：

<code class="java">class Solution {
    // 开始下标
    public static int start = -1;
    // 最大长度
    public static int maxLen= 0;
    public String longestPalindrome(String s) {
        start = -1;
        maxLen = 0;
        if(s==null||s.length()==0){
            return "";
        }
        for(int i=0;i<s.length();i++){
            // 以以后字符为对称轴
            judge(s,i,i);
            // 以以后字符和下一个字符的间隙为对称轴
            judge(s,i,i+1);
        }
        if(start == -1){
            return "";
        }
        return s.substring(start,start+maxLen);
    }

    public void judge(String s,int left,int right){
        while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        int size =  right-left-1;
        if(size > maxLen){
            maxLen = size;
            start = left+1;
        }
    }
}

动静布局

其实，一个字符串是回文串的话，那么它倒过去读也是一样的，也就是说，它与它反转后的字符串，其实是齐全匹配的，那么要是咱们用一个字符串和它反转字符串一一统计匹配，是不是就能够失去后果呢？

答案是必定的！假如原字符串为 s1，反转后的字符串为 s2，字符串长度为 n，咱们用数组 nums[n][n] 来记录匹配的数量，nums[i][j]示意以 s1[i] 结尾的字符子串，和以 s2[j]结尾的字符子串，两者的匹配字符的最大数值。

• 当 s1[i] == s2[j]:

  • 如果 i == 0 或者 j == 0: nums[i][j] = 1
  • 否则 nums[i][j] = nums[i - 1][j - 1] + 1;
• 如果 s1[i] ！= s2[j]，则 nums[i][j]=0

后面说的其实就是状态转移表达式，也就是 nums[i][j] 是怎么求解的？nums[i][j] 是依赖于 nums[i - 1][j - 1] 和 以后字符是否匹配，如果以后字符不匹配，间接赋值为 0，只有在以后字符匹配的状况下，才会须要看后面一位的匹配数值 nums[i - 1][j - 1]。

假如以 babad 为例子：

最初两行的计算：

实现的代码如下：

<code class="java">class Solution {
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        if (s.length() == 1) {
            return s;
        }
        int len = s.length();
        String s1 = new StringBuffer(s).reverse().toString();
        int[][] nums = new int[len][len];
        int end = 0, max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (s1.charAt(i) == s.charAt(j)) {
                    if (i == 0 || j == 0) {
                        nums[i][j] = 1;
                    } else {
                        nums[i][j] = nums[i - 1][j - 1] + 1;
                    }
                }
                if (nums[i][j] > max) {
                    if (len - i - 1 + nums[i][j] - 1 == j) {
                        end = j;
                        max = nums[i][j];
                    }
                }
            }
        }
        return s.substring(end - max+1, end+1);
    }
}

作者简介

【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。

剑指Offer全副题解PDF

2020年我写了什么？

开源编程笔记

喜欢 (0)赏

[搞代码]

分享 (0)