[LeetCode] 5. 最长回文子串 ☆☆☆(最长子串、动态规划)

最长回文子串 (动态规划法、中心扩展算法)

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/ （多解法）

描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

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

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

解析

将字符串倒序，然后对比形同的序列。----两字符串的公共子串。

字符串中的每个字符，向两边发散比较。注意有偶数子串、奇数子串。

代码（还有其他解法）

中心扩展算法

public String longestPalindrome_reconstructure2(String s) { // 第二次对代码进行重构

        if (s.length() < 2) { // 单个字符肯定是回文串，直接返回s

            return s;

        }

        int maxLength = 0;

        int center = 0;

        for (int i = 0; i < s.length(); i++){

            int begin = centerExpand(s, i, i);          // 最长回文串长度为奇数

            int end = centerExpand(s, i, i + 1);   // 最长回文串长度为偶数

            if (maxLength < Math.max(begin, end)){

                center = i;                                // 以center为中心

                maxLength = Math.max(begin, end);          // 最长回文串长度

            }

        }
        //如ababaabc,最后center为2，maxLength为5

        // 如果我们的回文串的长度为偶数，那么中心左边的长度会比右边的长度小1

        return s.substring(center - (maxLength - 1) / 2, center + maxLength / 2 + 1);

    }

    int centerExpand(String s, int begin, int end){

        int left = begin, right = end;

        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){

            left--;

            right++;

        }

        // 返回以begin,end为基准，同时向左向右扩展后能够得到的最长回文串长度（最后left较正确子串的值小1，right大1，所以这里减1。另一个1，由于下标的原因）

        return right - left - 1;

    }

[LeetCode] 5. 最长回文子串 ☆☆☆(最长子串、动态规划)的相关教程结束。