LeetCode_04_LongestPalindromicSubstring

1. question：最长回文子串（中等）

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

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

2. answer

思路：这道题为求解最长回文子串。

首先要判断什么是回文子串，奇数程度的话，除了中心点之外，两侧对称；偶数长度的话，两个对称。

最直观的就是暴力法遍历出所有的子串，然后判断子串是否是回文串，这显然是不行的。

回文串的判断有两种，

1. 由两边向中心遍历，比较。（此时我们需要限定一下两边，即先找到子串，再判断子串是不是回文串，这种由大到小，会造成很多无用的判断）
2. 由中心向两侧遍历，比较。（注意，此时给定子串也行，因为遍历的时候就是找子串的过程，并且小串不是回文串就没必要判断大串了，所以由小到大判断比较合适，采用这种方法）

代码如下所示：

public class Solution_0004 {

    public static int[] getSubString(char[] chars, int leftCenter, int rightCenter){

        // 根据中心，向外扩散，
        while(leftCenter >= 0 && rightCenter < chars.length){

            // 如果两个元素不相等，说明已经不是回文串了
            if(chars[leftCenter] != chars[rightCenter]){
                break;
            }

            // 分别向左向右遍历
            leftCenter --;
            rightCenter ++;
        }

        // 注意，跳出循环说明条件不满足，而上一个条件是满足的回文串
        return new int[]{leftCenter + 1, rightCenter - 1};
    }

    public static String longestPalindrome(String s) {

        char[] chars = s.toCharArray();
        int[] oddResult, evenResult;
        int left = 0, right = 0;
        int tempLeft, tempRight;

        for (int i = 0; i < s.length() - 1; i++) {
            // 遍历字符串，每个遍历元素都作为子串中心，向外遍历
            // 注意，字符串的长度有奇数和偶数之分，奇数和偶数判断是否是回文串的具体方法细节有区别
            // 奇数的字符串，中心只有一个；偶数的字符串，中心有两个

            // 奇数字符串
            oddResult = getSubString(chars, i, i);

            // 偶数字符串
            evenResult = getSubString(chars, i, i + 1);

            // 判断奇数和偶数字符串哪个长
            if(oddResult[1] - oddResult[0] >= evenResult[1] - evenResult[0]){
                tempLeft = oddResult[0];
                tempRight = oddResult[1];
            } else {
                tempLeft = evenResult[0];
                tempRight = evenResult[1];
            }

            // 判断得到的子串和之前的答案哪个长
            if(tempRight - tempLeft > right - left){
                right = tempRight;
                left = tempLeft;
            }

        }

        // 返回子串
        return s.substring(left, right + 1);
    }

    public static void main(String[] args) {

//        String s = "babad";
        String s = "cbbd";

        System.out.println(longestPalindrome(s));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)。